المپدیا

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

ابزار کاربر

ابزار سایت


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

جزایر گرد

در یک برکه، تعدادی نیلوفر آبی رشد کرده‌اند. هر نیلوفر آبی، یک برگ گرد دارد که روی آب گسترده می‌شود. یک حشره در نقطه‌ای از این برکه روی یکی از نیلوفرها قرار دارد. او می‌تواند روی یک نیلوفر راه برود، ولی برای حرکت در جایی که آب است باید شنا کند. او می‌خواهد از مکان خود به یک مکان دیگر که آن‌جا هم روی برگ نیلوفر قرار دارد مسافرت کند. ولی به علت خستگی می‌خواهد مسیری را طی کند که با کم‌ترین تعداد شنا به مقصد برسد. البته این حشره نمی‌تواند در یک شنا بیش از ۱ متر بپیماید وگرنه غرق خواهد شد. شما باید این مسیر را مشخص کنید.

ورودی

در سطر اول فایل ورودی $n$، تعداد نیلوفر‌ها آمده است. سپس در سطر بعد دو عدد حقیقی به نشانه‌ی مختصات اولیه‌ی مگس و در سطر بعد دو عدد حقیقی دیگر به نشانه‌ی مختصات مقصد آمده است. در $n$ سطر بعد، در هر سطر سه عدد حقیقی آمده است که دو عدد اول، مختصات مرکز یک نیلوفر و عدد سوم، شعاع آن نیلوفر می‌باشد.(شعاع هر نیلوفر بیش از صفر است.)تمام مسافت‌ها بر حسب سانتی‌متر هستند.

خروجی

در سطر اول فایل خروجی دو عدد $m$ و $k$ را به ترتیب بنویسید که اولی نشانگر کم‌ترین تعداد شناهای لازم برای رسیدن به مقصد است و دومی نشان‌دهنده‌ی تعداد نیلوفر‌هایی که مگس در سفر خود روی آن‌ها خواهد بود، است. سپس در $k$ سطر بعد به ترتیب، شماره‌ی نیلوفرهایی را که مگس در طول حرکتش روی آن‌ها خواهد بود را بنویسید.

توجه کنید که این نیلوفرها می‌توانند با هم سطحی مشترک داشته باشند یا بر هم مماس باشند. دراین صورت حشره می‌تواند با راه رفتن از یکی به روی دیگری برود.

محدودیت‌ها

  • محدودیت زمان: ۵ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت

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

ورودی نمونه خروجی نمونه
3
0.0 0.0 1.0
3.0 0.0 2.0
6.0 0.1 0.3
1 3
1
2
3

پاسخ


ابزار صفحه