3862 - 文物保护区

题目描述

某城市规划部门需要为 N 个重要文物设施划定一个文物保护区。每个文物设施的位置可以用二维平面上的点 (x, y) 表示。保护区域必须是一个边平行于 x 轴和 y 轴的矩形,且需要覆盖所有文物设施(允许文物设施位于矩形边界上)。

由于预算限制,城市规划部门决定最多移除 3 文物个设施,将他们移送到博物馆,以缩小保护区域的范围。

请帮助规划部门计算在移除最多 3 个设施后,能够覆盖剩余文物设施的最小矩形面积

输入

输入的第一行包含一个整数 N,表示文物设施的数量。

接下来的 N 行,每行包含两个整数 x_iy_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
说明

样例 1 说明

通过移除设施 (4, 100)(50, 7)(1, 1),我们得到了最小覆盖矩形面积为 20

因为移除上述 3 个文物设施之后,剩余文物设施的坐标分别为:7,8 15,9 8,12。其中 x 的最小值为 7 最大值为 15y 的最小值为 8 最大值为 12,因此面积 =(15-7) \times (12-8) = 32

数据范围

对于 10\% 的数据,满足 1 \le N \le 101 \le x_i,y_i \le 100

对于另外 10\% 的数据,满足 1 \le N \le 501 \le x_i,y_i \le 1000

对于 100\% 的数据,满足 5 \leq N \leq 500001 \leq x_i, y_i \leq 40000

标签
题目参数
时间限制 1 秒
内存限制 512 MB
提交次数 0
通过人数 0
金币数量 2 枚
难度 基础


上一题 下一题