Load Balancing

题目描述

农夫约翰的 $N$ 头奶牛分别站在二维农场上互不相同的位置 $(x_1, y_1) \ldots (x_n, y_n)$（$1 \leq N \leq 100,000$，并且 $x_i$ 与 $y_i$ 均为正的奇整数，且大小不超过 $1,000,000$）。FJ 想通过建造一条很长（可视为无限长）的南北方向栅栏来划分他的田地，其方程为 $x=a$（$a$ 为偶整数，从而保证栅栏不会穿过任何奶牛的位置）。他还想建造一条很长（可视为无限长）的东西方向栅栏，其方程为 $y=b$，其中 $b$ 为偶整数。这两条栅栏在点 $(a,b)$ 处相交，并将田地划分为四个区域。 FJ 希望选择 $a$ 和 $b$，使得四个区域中的奶牛数量尽量“均衡”，即没有任何一个区域包含过多的奶牛。令 $M$ 表示四个区域中奶牛数量的最大值，FJ 希望使 $M$ 尽可能小。请帮助他确定这个最小可能的 $M$ 值。

输入格式

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

输出格式

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

7
7 3
5 5
7 13
3 1
11 7
5 3
9 1

2

提示

题目来源：Brian Dean

标签: USACO|2016|Platinum

来源

USACO|2016|Platinum