【USACO16FEB】Load_Balancing_S

在二维平面上有 $n(1 \le n \le 1000)$ 个点，坐标为 $(x_i, y_i)$，保证 $x_i, y_i$ 均为 正奇数，且 $x_i, y_i \le 10^6$，没有任意两个点在同一个位置

现在需要你用 一条水平线 $y=b$ 和 一条竖直线 $x=a$ 将平面分割成 4 个区域（$a, b$ 都是 偶数），设 $c_1, c_2, c_3, c_4$ 是 4 个区域中点的个数，请你找到 $a, b$ 使得 $max(c_1, c_2, c_3, c_4)$ 最小，输出这个最小值

简单来说，就是让 点数最多的区域 的点数最少

输入格式

第一行包含 $1$ 个整数 $n$，表示点的个数

接下来 $n$ 行，每行包含 $x_i, y_i$

输出格式

输出 点数最多的区域 的最少点数

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

2

提示

【样例 1 解释】

【数据范围】

• $1 \le n \le 1000$
• $1 \le x_i, y_i \le 10^6$，$x_i, y_i$ 为正奇数

来源

• 参考答案