Processing math: 100%

المپدیا

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

ابزار کاربر

ابزار سایت


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

مسیر دور

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

ورودی

در فایل ورودی ابتدا در سطر اول n و سپس چهار عدد XA، YA، XB و YB به ترتیب آمده‌اند. سپس در n سطر بعد، در هر سطر سه عدد آمده‌اند که دو عدد اول مختصات مرکز و عدد سوم شعاع دایره می‌باشند. مختصات و شعاع‌ها حقیقی‌اند.

خروجی

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

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

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

ابزار صفحه