المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی انتخاب تیم:دوره ی ۱۲:سوال ۲

مسیر دور

در یک صفحه، $n$ دایره قرار دارند. دو نقطه‌ی $A$ و $B$ هم مشخص شده‌اند. می‌خواهیم کوتاه‌ترین مسیر از $A$ به $B$ را بیابیم که تمام طول مسیر داخل یا روی دایره‌ها باشد.

ورودی

در فایل ورودی ابتدا در سطر اول $n$ و سپس چهار عدد $X_A$، $Y_A$، $X_B$ و $Y_B$ به ترتیب آمده‌اند. سپس در $n$ سطر بعد، در هر سطر سه عدد آمده‌اند که دو عدد اول مختصات مرکز و عدد سوم شعاع دایره می‌باشند. مختصات و شعاع‌ها حقیقی‌اند.

خروجی

در فایل خروجی تنها یک عدد بنویسید: طول کوتاه‌ترین مسیر، با دو رقم اعشار و یا عبارت No Solution. فرض کنید $n<501$.

ورودي و خروجي نمونه

ورودي نمونه خروجي نمونه
2 0 0 1 0
0 0.5 0.5
1 0.5 0.5
1.41

ابزار صفحه