四等分(Quad Partition)

题目描述

在二维平面上，有 n 个点，坐标分别记为 (x_i, y_i)。请找出一条平行于X轴与一条平行于Y轴的直线，将二维平面分成四部分，且在这四块区域里，点的分布尽量均匀——记 a, b, c, d 为四块区域中点的数量，请找到一个划分方案，使 a, b, c, d 中的最大值最小。

为了避免某点坐标恰好穿过划分直线的情况，保证所有点的坐标都是奇数，并且规定划分直线的坐标只能选择偶数。

输入格式

第一行：一个整数 n。

第二行到第 n+1 行：第 i+1 行有两个奇数 x_i 和 y_i。

输出格式

单个整数：表示所有方案中，a, b, c, d 最大值的最小值。

样例输入 #1

4 1 1 1 5 5 5 5 1

样例输出 #1

1

数据范围

• 1 ≤ x_i, y_i < 200,000
• 保证有 x_1 ≤ x_2 ≤ x_3...≤ x_n
• 对于 30% 数据，1 ≤ n ≤ 100
• 对于 60% 数据，1 ≤ n ≤ 5000
• 对于 100% 数据，1 ≤ n ≤ 100,000

知识点与难度

本题涉及的知识点从属于 GESP 5级，难度等级：⭐⭐⭐。

测试点分布