المپدیا

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

ابزار کاربر

ابزار سایت


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

Birth

کوچک در جشن تولد $n$‌ سالگی خود دوستانش را دعوت کرده است. کیک تولد او به صورت یک دایره با شعاع $r$‌ است که $n$ شمع روی آن قرار دارد. مادر کوچک کیک را با $m$ برش مستقیم به قطعاتی تقسیم می‌کند و به دوستان می‌دهد.

کوچک می‌خواهد قطعه‌ی کیک خودش بیش‌تر از یک شمع داشته باشد و به دوستان نزدیکش هم کیک شمع‌دار بدهد.

برنامه‌ای بنویسید که:

  • وضعیت کیک، شمع‌ها و برش‌ها را از ورودی بخواند.
  • دریابد که آیا قطعه‌ای هست که بیش از یک شمع داشته باشد و این که چه تعدادی از قطعات کیک، شمع دارند.
  • پاسخ را در خروجی بنویسید.

ورودی

سطر نخست ورودی شامل اعداد صحیح $m،n$ و $r$ است ($1\leq n \leq 10^4$، $0\leq m \leq 1000$ و $1\leq r \leq 2000$) و مرکز کیک روی مبدا مختصات قرار دارد.

در هر یک از $n$ سطر بعدی، مختصات یک شمع به صورت دو عدد صحیح $x_i$ و $y_i$ آمده است. شمع‌ها را به صورت نقطه در نظر بگیرید. مختصات تمام شمع‌ها متفاوت است و هیچ شمعی خارج از کیک قرار ندارد.

در هر یک از $m$ سطر دیگر، اعداد صحیح $b_i،a_i$ و $c_i$ آمده‌اند که هر کدام معادله‌ی یک برش را به صورت $a_ix+b_iy+c_i=0$ نشان می‌دهد ( $-10^4 \leq a_i,b_i,c_i \leq 10^4$). در ضمن هیچ شمعی روی هیچ برشی قرار ندارد.

خروجی

اگر قطعه‌ای شامل بیش از یک شمع وجود دارد، در سطر اول خروجی عبارت $YES$ و در غیر این صورت $NO$ چاپ کنید. در سطر دوم خروجی، تعداد قطعات شامل شمع را چاپ کنید.

محدودیت‌ها

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

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

ورودی نمونه خروجی نمونه
3 2 3
2 2
1 -1
-2 0
1 1 -1
0 1 -1
YES
2
3 2 3
2 2
1 -1
-2 0
2 -1 0
0 1 -1
NO
3

ابزار صفحه