P6812: 负载平衡

---

【题目描述】

【题目描述】
农民约翰的N头奶牛分别站在他二维农场(1≤N≤100,xi和yi是大小不超过B的正奇数)的不同位置(x1,y1)…(xn,yn)。FJ想通过等式x=a (a将是偶数，从而确保他不会通过任何奶牛的位置建立篱笆，通过建立一个长(实际上是无限长)的南北篱笆来划分他的田地。他还想建立一个东西方向的长(实际上是无限长)栅栏方程y=b，其中b是一个偶数。这两个栅栏在点(a,b)相交，它们一起把他的场地分成四个区域。
FJ希望选择a和b，以便出现在四个结果区域中的奶牛是合理的“平衡”的，没有一个区域包含太多的奶牛。假设M是四个区域中出现的奶牛的最大数量，FJ想让M尽可能小。请帮他确定这个M的最小可能值。
对于前五个测试用例，B保证最多为100。在所有测试用例中，B保证最多为1,000,000。

【输入格式】（balancing.in）：

输入的第一行包含两个整数，N和B。接下来的N行分别包含一头奶牛的位置，指定其x和y坐标。
【输出格式】（balance.out）：
你应该输出最小的M值，FJ可以通过最优地定位他的围栏来实现。。
【样例输入】：
7 10
7 3
5 5
9 7
3 1
7 7
5 3
9 1
 
【样例输出】：
2

题目类型~

USACO-2016-铜-3 

咻咻~

提交答案 状态 返回