====== Similar Polygons ====== به دو چندضلی شبیه می‌گوییم اگر بتوان یکی از آن‌ها را با جابه‌جا کردن و ‎scale‎ کردن به دیگری تبدیل کرد. به یک چندضلعی طبیعی می‌گوییم اگر همه رئوس آن دارای ‎$x$‎ و ‎$y$‎ صحیح باشند. عدد یک چند ضلعی برابر است با تعداد نقاط با مختصات صحیح ‎$(x,y)$‎ که کاملاً درون چندضلعی قرار دارند و روی محیط آن قرار ندارند. ‎ به شما یک چندضلعی طبیعی محدب داده شده است. شما باید کوچک‌ترین ‎$k$‎ را بیابید به‌طوری‌که ‎$m$‎ چندضلعی طبیعی شبیه آن با مساحت‌های متفاوت وجود داشته باشند که جمع اعداد آن‌ها برابر با ‎$k$‎ شود. ===== ورودی ===== * در سطر اول ورودی دو عدد ‎$1 \leq n \leq 1000$‎ نشانگر تعداد رئوس چندضلعی و ‎$1 \leq m \leq 1000000$‎ آمده است.‎ * در ‎$n$‎ سطر بعد، هر سطر دو عدد ‎$x_i$‎ و ‎ $y_i$‎آمده است که رئوس چندضلعی را به‌صورت ساعت‌گرد یا پادساعت‌گرد نشان می دهند.‎ * تمامی اعداد ورودی بین ‎$-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 | * [[سوال ۲۳|سوال بعد]] * [[سوال ۲۱|سوال قبل]]