某城市规划部门需要为 N 个重要文物设施划定一个文物保护区。每个文物设施的位置可以用二维平面上的点 (x, y) 表示。保护区域必须是一个边平行于 x 轴和 y 轴的矩形,且需要覆盖所有文物设施(允许文物设施位于矩形边界上)。
由于预算限制,城市规划部门决定最多移除 3 文物个设施,将他们移送到博物馆,以缩小保护区域的范围。
请帮助规划部门计算在移除最多 3 个设施后,能够覆盖剩余文物设施的最小矩形面积。
输入的第一行包含一个整数 N,表示文物设施的数量。
接下来的 N 行,每行包含两个整数 x_i 和 y_i,表示第 i 个文物设施的坐标。
输出一个整数,表示在移除最多 3 个文物设施后,覆盖剩余文物设施的最小矩形面积。
6 1 1 7 8 15 9 8 12 4 100 50 7
32
8 1 200 15 18 123 29 30 50 1 101 3 4 20 10 39 19
1656
10 10 20 30 50 70 90 1 100 1 200 200 10 30 80 35 52 90 100 100 10
7120
通过移除设施 (4, 100)、(50, 7) 和 (1, 1),我们得到了最小覆盖矩形面积为 20。
因为移除上述 3 个文物设施之后,剩余文物设施的坐标分别为:7,8 15,9 8,12。其中 x 的最小值为 7 最大值为 15,y 的最小值为 8 最大值为 12,因此面积 =(15-7) \times (12-8) = 32。
对于 10\% 的数据,满足 1 \le N \le 10,1 \le x_i,y_i \le 100。
对于另外 10\% 的数据,满足 1 \le N \le 50,1 \le x_i,y_i \le 1000。
对于 100\% 的数据,满足 5 \leq N \leq 50000,1 \leq x_i, y_i \leq 40000。