گاوهای کشاورز جان در نقاط مختلف هستند (x
1,y
1)…(x
n,y
n ) فیلدهای آن (1≤N≤100000، همه x
i و y
i اعداد صحیح فرد مثبتی هستند که از 1،000،000 تجاوز نمی‌کنند. FD می‌خواهد میدان خود را با یک حصار بینهایت تقسیم کند. طول از شمال به جنوب که با معادله x=a توصیف می‌شود (a یک عدد صحیح زوج است، بنابراین اطمینان حاصل می‌شود که حصار از موقعیت هیچ گاوی عبور نمی‌کند.) او همچنین می‌خواهد حصاری با طول بینهایت بسازد. از شرق به غرب، که با معادله y=b توصیف می‌شود، جایی که b یک عدد صحیح زوج است.
FD می خواهد a و b را به گونه ای انتخاب کند که آنها یک "متعادل" دریافت کنند. تعداد گاو در تمام مناطق، به عنوان مثال. به طوری که هیچ منطقه ای وجود ندارد که گاوهای زیادی داشته باشد. فرض کنید M حداکثر تعداد گاوها در این چهار منطقه باشد، FD می خواهد M تا حد امکان کوچک باشد. به FD کمک کنید تا این حداقل مقدار ممکن را برای M.
تعیین کند
فرمت ورودی:
خط اول ورودی شامل یک عدد صحیح N است. هر یک از n خط بعدی حاوی محل یک گاو است که با مختصات x و y آن مشخص می شود.
فرمت خروجی:
حداقل مقدار ممکن M را که می تواند با چیدمان بهینه نرده ها به PD برسد چاپ کنید.
<بدن>
|
وارد کنید |
خروجی |
|
7
73
5 5
7 13
3 1
117
5 3
9 1
|
2 |