Module: 三元搜索


Problem

7 /9


负载均衡

Problem

<分区> Farmer John 的奶牛在不同的点 (x1,y1)…(xn,yn ) 它的字段(1≤N≤100,000, xi 和yi 都是不超过1,000,000 的正奇数。FD 想用无穷大的栅栏来划分他的字段从北到南的长度，用方程x=a来描述（a是偶数，所以保证围栏不经过任何牛的位置。）他还想建一个无限长的围栏从东到西，由方程y=b描述，其中b为偶数这两个栅栏相交于（a,b），共同将场地分成四个区域。
<分区> FD 想要以这样的方式选择 a 和 b，使他们获得“平衡”所有地区的奶牛数量，即这样就没有包含太多奶牛的区域。令 M 为这四个区域中奶牛的最大数量，FD 希望 M 越小越好。帮助 FD 确定 M 的最小可能值。
<分区>  
<分区> 输入格式：
<分区> 输入的第一行包含一个整数 N。接下来的 n 行中的每一行包含一头牛的位置，由它的 x 和 y 坐标表示。
<分区> 输出格式：
<分区> 打印最优排列栅栏时达到 PD 的 M 的最小可能值。

<正文>

time 1000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Your Program

Attach a file with the source code of the program:

or select a programming language and type your program

Auto

       

Program check result To check the solution of the problem, you need to register or log in!

输入 输出
<分区> 7 <分区> 73 <分区> 5 5 <分区> 7 13 <分区> 3 1 <分区> 117 <分区> 5 3 <分区> 9 1 2