Loading [MathJax]/jax/output/HTML-CSS/jax.js

المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:متفرقه:آزمون های اینترنتی ۸۹ تا ۹۱:سوال ۲۲

Similar Polygons

به دو چندضلی شبیه می‌گوییم اگر بتوان یکی از آن‌ها را با جابه‌جا کردن و ‎scale‎ کردن به دیگری تبدیل کرد. به یک چندضلعی طبیعی می‌گوییم اگر همه رئوس آن دارای ‎x‎ و ‎y‎ صحیح باشند. عدد یک چند ضلعی برابر است با تعداد نقاط با مختصات صحیح ‎(x,y)‎ که کاملاً درون چندضلعی قرار دارند و روی محیط آن قرار ندارند. ‎ به شما یک چندضلعی طبیعی محدب داده شده است. شما باید کوچک‌ترین ‎k‎ را بیابید به‌طوری‌که ‎m‎ چندضلعی طبیعی شبیه آن با مساحت‌های متفاوت وجود داشته باشند که جمع اعداد آن‌ها برابر با ‎k‎ شود.

ورودی

  • در سطر اول ورودی دو عدد ‎1n1000‎ نشانگر تعداد رئوس چندضلعی و ‎1m1000000‎ آمده است.‎
  • در ‎n‎ سطر بعد، هر سطر دو عدد ‎xi‎ و ‎ yi‎آمده است که رئوس چندضلعی را به‌صورت ساعت‌گرد یا پادساعت‌گرد نشان می دهند.‎
  • تمامی اعداد ورودی بین ‎1000000‎ و ‎1000000‎ قرار دارند.

خروجی

در تنها سطر خروجی عدد ‎k‎ را به پیمانه‌ی ‎1000081‎ چاپ نمایید.‎

محدودیت‌ها

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

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

ورودی نمونه خروجی نمونه
4 1‎
0 0‎
0 1‎
1 1‎
1 0
0
4 2‎
0 0‎
0 1‎
1 1
‎1 0
1
4 10‎
0 0‎
0 1‎
1 1
‎1 0
285

ابزار صفحه