توجد أبقار المزارع جون في نقاط مختلفة (x
1 ، y
1 ) & hellip؛ (x
n ، y
n ) حقولها (1 & le؛ N & le؛ 100،000 ، كل 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 |