- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
سارا در مرکز محور مختصات ایستاده است و تکان نمی‌خورد. اطراف او $n$ سیبل وجود دارد که او می‌خواهد به سمت آن‌ها تیر اندازی کند. سارا می‌خواهد با کمترین تعداد گلوله‌ی ممکن تمام سیبل‌ها را سوراخ کند. سارا برای اینکار به حداقل چند گلوله نیاز دارد؟
همچنین میدانیم گلوله‌های سارا بسیار با کیفیت هستند و بعد از برخورد با یک سیبل بدون تغییر جهت به مسیر خود ادامه می‌دهند و اگر باز هم سیبلی در مسیرشان بود آن‌ها را هم سوراخ می‌کنند. همچنین اگر مسیر یک گلوله تنها با نقطه‌ی گوشه‌ی یک سیبل برخورد داشته باشد (مماس باشد) آن سیبل سوراخ می‌شود.
در شکل زیر سیبل‌ها با رنگ قرمز مشخص شده‌اند و یک خط فرضی شلیک برای سارا با خط هاشور خورده‌ی سبز نشان داده شده است. این جهت شلیک، دو تا از سیبل‌ها را سوراخ می‌کند.
ورودی
در سطر اول ورودی، عدد طبیعی $n$ که تعداد سیبل‌ها است داده شده است. $$1\leq n \leq 100,000$$
در $t$ سطر بعدی، در هر سطر اطلاعات یک سیبل داده شده است. هر سیبل با دادن چهار عدد $x_1, y_1, x_2, y_2,$ مشخص می‌شود که $(x_1,y_1)$ مختصات یک سر سیبل و $(x_2,y_2)$ مختصات سر دیگر سیبل است.
$$-10^9\leq x_1,x_2 \leq 10^9$$ $$-10^9\leq y_1,y_2 \leq 10^9$$
همچنین میدانیم هیچ سیبلی از روی سارا (نقطه‌ی $(0, 0)$) عبور نمی‌کند و همچنین اگر هر سیبل را از دو طرفش ادامه دهیم این خط هم با سارا (نقطه‌ی $(0, 0)$) برخورد نمی‌کنند.
خروجی
حداقل تعداد گلوله‌ی مورد نیاز برای سوراخ کردن تمام سیبل‌ها را در تنها سطر خروجی چاپ کنید.
مثال‌ها
ورودی نمونه ۱
4
0 1 1 0
2 0 0 -1
0 -3 -1 0
-5 0 0 4
خروجی نمونه ۱
2
توضیح نمونه ۱
اگر ۲ شلیک را مانند شکل زیر انجام دهد هر ۴ سیبل را سوراخ کرده است.
ورودی نمونه ۲
6
-1 2 -2 1
-5 5 6 5
-5 -6 6 5
-5 5 -5 -6
-2 1 -2 -1
-1 2 0 2
خروجی نمونه ۲
3
توضیح نمونه ۲
اگر ۳ شلیک را مانند شکل زیر انجام دهد هر ۶ سیبل را سوراخ کرده است.
ارسال پاسخ برای این سؤال