بادکنک ترکانی


  • محدودیت زمان: 2 ثانیه
  • محدودیت حافظه: 50 مگابایت

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

تیرها فقط در جهت مثبت محور x رها می‌شوند. اگر دو بادکنک مماس بر یکدیگر باشند،‌ تیر پرتابی به مماس آن‌ها هردوی بادکنک‌ها را می‌ترکاند.

برنامه‌ای بنویسید که با گرفتن تعداد بادکنک‌ها در سطر اول و سپس مختصات مرکز و شعاع،‌ تعداد تیرهای لازم را چاپ کند.

محدودیت‌ها🔗

1n1071 \leq n \leq 10^7 104x,y104-10^4 \leq x,y \leq 10^4 r50 r \leq 50

ورودی🔗

در خط اول n تعداد بادکنک‌ها و در n خط بعدی مختصات مرکز و شعاع بادکنک‌ها

خروجی🔗

تعداد تیرهای لازم برای ترکاندی بادکنک‌ها

مثال🔗

نمونه ورودی:

5
2 2 1.5
3 3 1
1 9 1.2
4 -2 2
3 -5 3
Plain text

نمونه خروجی:

3
Plain text
ارسال پاسخ برای این سؤال
در حال حاضر شما دسترسی ندارید.