אמש ראיתי אותך רץ

בשדות החסד הפתוחים

כבר לא היית שבור או שרוי בכאב.[^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

2.00000000

הסבר 1

מלבן שארבעת קודקודיו הם $(-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

הסבר 2

האיור הבא מציג את הקטעים שבקלט. שימו לב שהקטעים עשויים להיחתך:

איור 1: הסבר לדוגמה 2

אפשר לבנות סידור בעל כל אורך כולל הגדול מהתשובה באמצעות התקרבות ללא גבול לעקומות האדומות האלה. שימו לב שמדוגמה 1 קל להבין שהקטע האדום בפינה השמאלית העליונה נספר פעמיים.

קלט 3

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

פלט 3

13.656854249492380195206754896839

הסבר 3

התשובה היא $8+4\sqrt{2}$.

ההסבר מוצג באיור:

איור 2: הסבר לדוגמה 3

אפשר לבנות סידור בעל כל אורך כולל הגדול מ־$8+4\sqrt{2}$ באמצעות התקרבות ללא גבול לעקומות האדומות האלה.

דוגמה 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$. מובטח ששני קצות הקטע שונים זה מזה, שקטעים שונים אינם משתמשים באותה נקודה, ושאין שלוש נקודות הנמצאות על ישר אחד.

[^1]: מילות השיר שבנוסח השאלה לקוחות מתוך Open Fields of Grace של Jackie Evancho; המלחינים הם Lisa Venkatrathnam ו־Paul Sumares.