ليلة أمس رأيتك تركض
في حقول النعمة المفتوحة
لم تعد محطماً أو تتألم[^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$. يُضمن أن طرفي كل قطعة مختلفان، وأن القطع المختلفة لا تشترك في نقاط طرفية، وأن أي ثلاث نقاط ليست على استقامة واحدة.