Courses

एल्गोरिदम

ज्यामिति

Module: ज्यामिति

Problem

6 /7

सुरक्षित मार्ग

Problem

<दिव> पेट्या और वस्या - अच्छे दोस्त हैं। इसलिए, वे अक्सर एक-दूसरे से मिलने जाते हैं। हाल ही में पेट्या

<दिव> ड्राइवर का लाइसेंस मिला है और वह अपने दोस्त से मिलने जा रहा है। सरलता के लिए, हम मान लेंगे कि

<दिव> जिस शहर में वे रहते हैं, उसकी सभी सड़कें अंतहीन सीधी रेखाएँ हैं। चौराहे पर

<दिव> दो या दो से अधिक सड़कें चौराहे हैं। पेट्या और वस्या के घर कुछ के पास स्थित हैं

<दिव> शहर की सड़कें, लेकिन चौराहों पर नहीं।

<दिव> पेट्या अपने घर के पास सड़क पर अपनी यात्रा शुरू करती है। साथ ही वह

में से कोई भी चुन सकता है <दिव> दो दिशाएँ। जब पेट्या चौराहे पर पहुंचती है, तो वह किसी और की ओर मुड़ सकती है

<दिव> इससे गुजरने वाली सड़क या वर्तमान के साथ ड्राइव करना जारी रखें। चूँकि पेट्या बहुत अच्छी नहीं है

<दिव> एक अनुभवी ड्राइवर, वह हर मोड़ पर उसे चिंतित करता है। और

<दिव> पेट्या की उत्तेजना उस कोण के बराबर है जिससे वह डिग्री में मुड़ता है। उदाहरण के लिए,

के साथ <दिव> समकोण पर पेट्या का उत्साह 90 है।

कम तीखे मोड़ के साथ, पेट्या कम चिंता करती है, और एक तेज मोड़ के साथ - mdash; मजबूत।

हम मानेंगे कि पूरे मार्ग में पेट्या का उत्साह मूल्यों के योग के बराबर है <दिव> आंदोलन के दौरान उसे कोणों की डिग्री बदलनी होगी। बेशक, पेट्या चाहती हैं <दिव> ऐसा रास्ता चुनें जिससे उसे कम से कम चिंता हो। <दिव> पेट्या को यह पता लगाने में मदद करें कि वह कम से कम कुल कितने उत्साह का अनुभव करेगा, <दिव> वस्या के घर पहुँच कर। <दिव> इनपुट डेटा प्रारूप <दिव> इनपुट फ़ाइल की पहली पंक्ति में एक पूर्णांक n (1 ≤ n ≤ 50) — में सड़कों की संख्या <दिव> शहर। अगली n पंक्तियों में सड़कों का वर्णन है। <दिव> प्रत्येक सड़क को चार पूर्णांक x1, y1, x2, y2 द्वारा वर्णित किया गया है, जो निर्देशांक द्वारा दिए गए हैं <दिव> दो अलग-अलग बिंदु (X1, y1) और (x2, y2) जिनसे होकर सड़क गुजरती है। <दिव> यह गारंटी है कि कोई भी दो सड़कें एक जैसी नहीं होतीं। अगली दो पंक्तियों में है <दिव> पेट्या और वस्या के घरों के निर्देशांक। यह गारंटी है कि प्रत्येक घर ठीक एक सड़क पर है, <दिव> और यह भी कि पेट्या और वस्या अलग-अलग जगहों पर रहते हैं। <दिव> इनपुट फ़ाइल में सभी बिंदुओं के निर्देशांक पूर्णांक हैं और 100 से से अधिक नहीं हैं <दिव> पूर्ण मूल्य। <दिव>
आउटपुट स्वरूप <दिव> आउटपुट फ़ाइल में एक ही नंबर प्रिंट करें — कुल कोण, डिग्री में, जिसके द्वारा <दिव> मार्ग के इष्टतम विकल्प के साथ पेट्या को मुड़ना होगा। उत्तर को सही माना जाता है यदि <दिव> इसकी सापेक्ष या पूर्ण त्रुटि 10&ऋण 9 से अधिक नहीं है। <दिव> यदि पेट्या वस्या के घर नहीं पहुंच पाती है, तो नंबर −1 प्रिंट करें।
उदाहरण
इनपुट
<दिव> 3 <दिव> 0 0 2 0 <दिव> 1 1 0 2 <दिव> 1 2 3 2 <दिव> -3 0 <दिव> 3 2
निष्कर्ष
270.0

इनपुट
<दिव> 1 <दिव> 0 0 2 0 <दिव> 0 0 <दिव> 20
निष्कर्ष
0.0

इनपुट
<दिव> 5 <दिव> 0 0 1 0 <दिव> 0 0 1 1 <दिव> 0 0 0 1 <दिव> 0 0 -1 1 <दिव> 0 1 1 1 <दिव> 50 <दिव> 05
निष्कर्ष
90.0

<दिव> निम्नलिखित आंकड़ा पहले उदाहरण से मेल खाता है। पेट्या दो 135 चक्कर लगाती है <दिव> डिग्री, इसकी कुल तरंग 270 है।