เมื่อคืนฉันเห็นเธอวิ่ง

ในทุ่งกว้างแห่งพระกรุณา

เธอไม่แตกสลายหรือเจ็บปวดอีกต่อไป[^1]

คุณพบทุ่งกว้างสุดลูกหูลูกตา ที่นั่นคุณลืมอดีตที่เคยแตกสลายและเจ็บปวด วิ่งเล่นราวกับเด็กท่ามกลางพระพรของพระเจ้า

แต่คุณพบปัญหาว่าในทุ่งนี้มีหุบเหวหลายแห่ง คุณอาจตกลงไปได้ทุกเมื่อ เพื่อให้วิ่งเล่นได้อย่างอิสระต่อไป คุณจึงตัดสินใจล้อมหุบเหวเหล่านี้ด้วยรั้ว

เราสามารถละเลยความกว้างของหุบเหวและมองแต่ละแห่งเป็นส่วนของเส้นตรง ส่วนของเส้นตรงเหล่านี้อาจตัดกันได้ รั้วของคุณต้องเป็น เส้นโค้งปิดหนึ่งเส้นหรือหลายเส้นที่ไม่ตัดตัวเองและไม่ตัดกันเป็นคู่ ๆ โดย หุบเหวทุกแห่งต้องอยู่ภายในบริเวณปิดที่ล้อมด้วยเส้นโค้งปิดเส้นใดเส้นหนึ่งทั้งหมด

แน่นอนว่าการทำรั้วต้องใช้ทรัพยากร โดยปริมาณทรัพยากรแปรผันตรงกับความยาวรั้ว คุณต้องการใช้ทรัพยากรรวมน้อยที่สุด จึงต้องหาค่า ขอบเขตล่างมากที่สุด ของความยาวรั้วรวม กล่าวคือหาจำนวนจริง $x$ ที่มากที่สุด ซึ่งไม่มีวิธีใดทำให้ความยาวรั้วรวมน้อยกว่า $x$

ข้อมูลนำเข้า

อ่านข้อมูลจากไฟล์ fields.in

บรรทัดแรกมีจำนวนเต็ม $n$ หมายถึงจำนวนหุบเหว

จากนั้นมี $n$ บรรทัด บรรทัดที่ $i$ มีจำนวนเต็มสี่จำนวน $a_i,b_i,c_i,d_i$ หมายถึงหุบเหวที่ $i$ เป็นส่วนของเส้นตรงเชื่อมจุด $(a_i,b_i)$ กับ $(c_i,d_i)$ รับประกันว่าปลายทั้งสองไม่ตรงกัน ส่วนของเส้นตรงต่างเส้นไม่มีจุดปลายร่วมกัน และไม่มีจุดสามจุดใดอยู่บนเส้นตรงเดียวกัน

ข้อมูลส่งออก

เขียนผลลัพธ์ลงไฟล์ fields.out

ส่งออกหนึ่งบรรทัดที่มีจำนวนจริงหนึ่งจำนวน คือขอบเขตล่างมากที่สุดของความยาวรั้วรวม ค่าที่น้อยกว่าระหว่างความคลาดเคลื่อนสัมบูรณ์และความคลาดเคลื่อนสัมพัทธ์จากคำตอบมาตรฐานต้องไม่เกิน $10^{-6}$

ตัวอย่าง

ข้อมูลนำเข้า 1

1
0 0 0 1

[^1]: เนื้อเพลงในโจทย์มาจากเพลง Open Fields of Grace ของ Jackie Evancho ประพันธ์โดย Lisa Venkatrathnam และ Paul Sumares

ข้อมูลส่งออก 1

2.00000000

หมายเหตุ

สี่เหลี่ยมผืนผ้าที่มีจุดยอด $(-0.01,-0.01),(-0.01,1.01),(0.01,1.01),(0.01,-0.01)$ ครอบส่วนของเส้นตรงที่กำหนดไว้อย่างสมบูรณ์ และมีความยาวรอบรูป $2.08$ ซึ่งมากกว่าขอบเขตล่างมากที่สุดเล็กน้อย

เราพิสูจน์ได้ว่าไม่มีวิธีที่มีความยาวเท่ากับ $2$ พอดี แต่สามารถ “บีบ” สี่เหลี่ยมจัตุรัสเข้าหาส่วนของเส้นตรงที่กำหนดได้ใกล้เท่าใดก็ได้ เพื่อสร้างวิธีที่มีความยาวเป็นค่าใด ๆ ที่มากกว่า $2$

ข้อมูลนำเข้า 2

4
-1 7 0 7
0 0 0 1
2 -3 5 5
2 2 6 -1

ข้อมูลส่งออก 2

23.563573998194637061425470524757

หมายเหตุ

ภาพต่อไปนี้แสดงส่วนของเส้นตรงที่กำหนด โปรดสังเกตว่าส่วนของเส้นตรงสามารถตัดกันได้:

ภาพที่ 1: คำอธิบายตัวอย่างที่ 2

เราสามารถสร้างวิธีที่มีความยาวรวมเป็นค่าใด ๆ ที่มากกว่าคำตอบได้ โดย “เข้าใกล้” เส้นโค้งสีแดงเหล่านี้มากขึ้นเรื่อย ๆ จากตัวอย่างที่ 1 จะเห็นได้ง่ายว่าส่วนของเส้นตรงสีแดงที่มุมซ้ายบนถูกนับสองครั้ง

ข้อมูลนำเข้า 3

4
-1 1 -1 3
0 4 2 4
3 1 3 3
0 0 2 0

ข้อมูลส่งออก 3

13.656854249492380195206754896839

หมายเหตุ

คำตอบคือ $8+4\sqrt2$

คำอธิบายดังภาพ:

ภาพที่ 2: คำอธิบายตัวอย่างที่ 3

เราสามารถสร้างวิธีที่มีความยาวรวมเป็นค่าใด ๆ ที่มากกว่า $8+4\sqrt2$ ได้ โดย “เข้าใกล้” เส้นโค้งสีแดงเหล่านี้มากขึ้นเรื่อย ๆ

ตัวอย่าง 4

ดูไฟล์ fields/fields4.in และ fields/fields4.ans ในไดเรกทอรีของผู้เข้าแข่งขัน

ข้อจำกัด

สำหรับ $5\%$ ของข้อมูล รับประกันว่า $1\le n\le1$

สำหรับ $10\%$ ของข้อมูล รับประกันว่า $1\le n\le2$

สำหรับ $15\%$ ของข้อมูล รับประกันว่า $1\le n\le10$

สำหรับ $30\%$ ของข้อมูล รับประกันว่า $1\le n\le15$

สำหรับ $45\%$ ของข้อมูล รับประกันว่า $1\le n\le30$

สำหรับ $55\%$ ของข้อมูล รับประกันว่า $1\le n\le60$

สำหรับ $65\%$ ของข้อมูล รับประกันว่า $1\le n\le120$

สำหรับ $75\%$ ของข้อมูล รับประกันว่า $1\le n\le200$

สำหรับข้อมูลอีก $10\%$ รับประกันว่าคำตอบประกอบด้วยเส้นโค้งไม่เกินสองเส้น

สำหรับ $100\%$ ของข้อมูล รับประกันว่า $1\le n\le250$ และ $0\le|a_i|,|b_i|,|c_i|,|d_i|\le10^9$ รับประกันว่าปลายทั้งสองไม่ตรงกัน ส่วนของเส้นตรงต่างเส้นไม่มีจุดปลายร่วมกัน และไม่มีจุดสามจุดใดอยู่บนเส้นตรงเดียวกัน