5094：文物保护区
文件提交：无需freopen
内存限制：512 MB
时间限制：1.000 S
评测方式：普通裁判
金币值：
命题人：
提交：1
解决：0
题目描述
# 文物保护区
## 题目描述
某城市规划部门需要为 $N$ 个重要文物设施划定一个文物保护区。每个文物设施的位置可以用二维平面上的点 $(x, y)$ 表示。保护区域必须是一个**边平行于 $x$ 轴和 $y$ 轴的矩形**，且需要覆盖所有文物设施（允许文物设施位于矩形边界上）。
由于预算限制，城市规划部门决定**最多**移除 $3$ 文物个设施，将他们移送到博物馆，以缩小保护区域的范围。
请帮助规划部门计算在移除**最多** $3$ 个设施后，能够覆盖剩余文物设施的**最小矩形面积**。
## 输入格式
输入的第一行包含一个整数 $N$ ，表示文物设施的数量。
接下来的 $N$ 行，每行包含两个整数 $x_i$ 和 $y_i$ ，表示第 $i$ 个文物设施的坐标。
## 输出格式
输出一个整数，表示在移除最多 $3$ 个文物设施后，覆盖剩余文物设施的最小矩形面积。
## 样例
### 样例输入 1
```text
6
1 1
7 8
15 9
8 12
4 100
50 7
```
### 样例输出 1
```text
32
```
### 样例输入 2
```text
8
1 200
15 18
123 29
30 50
1 101
3 4
20 10
39 19
```
### 样例输出 2
```text
1656
```
### 样例输入 3
```text
10
10 20
30 50
70 90
1 100
1 200
200 10
30 80
35 52
90 100
100 10
```
### 样例输出 3
```text
7120
```
## 说明/提示
样例 $1$ 说明
通过移除设施 $(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$ 。
---
**题目来源：** 25年3月-C组（大咖）