Load Balancing

题目描述

农夫约翰的 $N$ 头奶牛分别站在他二维农场上互不相同的位置 $(x_1, y_1) \ldots (x_n, y_n)$（$1 \leq N \leq 100$，且所有 $x_i$ 与 $y_i$ 均为不超过 $B$ 的正奇整数）。FJ 想通过建造一条很长（可视为无限长）的南北向栅栏来划分他的土地，其方程为 $x=a$（$a$ 将是一个偶整数，从而保证栅栏不会穿过任何奶牛的位置）。他还想建造一条很长（可视为无限长）的东西向栅栏，其方程为 $y=b$，其中 $b$ 为偶整数。这两条栅栏在点 $(a,b)$ 处相交，并将农场划分为四个区域。

FJ 希望选择 $a$ 和 $b$，使得四个区域中的奶牛数量尽量“均衡”，即没有任何一个区域包含过多的奶牛。设 $M$ 为四个区域中奶牛数量的最大值，FJ 希望让 $M$ 尽可能小。请帮助他求出这个 $M$ 的最小可能值。

对于前五个测试用例，保证 $B$ 至多为 100。在所有测试用例中，保证 $B$ 至多为 1,000,000。

输入格式

第一行包含两个整数 $N$ 和 $B$。接下来的 $n$ 行每行给出一头奶牛的位置，包含其 $x$ 与 $y$ 坐标。

输出格式

输出在最优放置栅栏的情况下，FJ 能达到的 $M$ 的最小可能值。

7 10
7 3
5 5
9 7
3 1
7 7
5 3
9 1

2

提示

题目来源：Brian Dean

标签: USACO|2016|Bronze

来源

USACO|2016|Bronze