- 矩形选择
XJOI - 题目ID：15845必做题100分
最新提交：
0 分
历史最高：
0 分
时间限制: 1000ms
空间限制: 262144kB
题目描述
时间限制：1s 空间限制：256MB
题目描述
有
2
×
�
2×n个数，两两可以任意组合凑出
�
n个坐标点，需要用一个平行于
�
x轴和
�
y轴的矩形将
�
n个点括起来，点可以重合。现在问需要将
�
n个点括起来，矩形的面积至少为多少（矩形的面积可以为
0
0）。
输入格式
从文件Rectangle.in中读入数据。
第一行输入一个正整数
�
(
1
≤
�
≤
1
0
5
)
n(1≤n≤10
5
)，表示需要用矩形括起来的点的数量。
第二行输入
2
×
�
2×n 个整数
�
1
,
�
2
,
.
.
.
,
�
2
�
(
1
≤
�
�
≤
1
0
9
)
a
1
,a
2
,…,a
2n
(1≤a
i
≤10
9
)，表示用来组合成坐标的数。
输出格式
输出到文件Rectangle.out中。
输出一个整数，表示最小的矩形面积。
样例#1
输入样例#1
4
4 1 3 2 3 2 1 3
输出样例#1
1
样例#2
输入样例#2
3
5 8 5 5 7 5
输出样例#2
0
提示/说明
对于样例#1，我们可以选择点
(
1
,
3
)
,
(
1
,
3
)
,
(
2
,
3
)
,
(
2
,
4
)
(1,3),(1,3),(2,3),(2,4)，那么矩形的最小面积为
1
1（左下角为
(
1
,
3
)
(1,3)，右上角为
(
2
,
4
)
(2,4)）。
对于样例#2，我们可以选择点
(
5
,
5
)
,
(
7
,
5
)
,
(
8
,
5
)
(5,5),(7,5),(8,5)，此时举行的面积为
0
0，因为一条直线即可覆盖所有点。
数据范围
测试点编号
�
≤
n≤
1
∼
2
1∼2
20
20
3
∼
5
3∼5
1
×
1
0
2
1×10
2
6
∼
10
6∼10
1
×
1
0
3
1×10
3
11
∼
20
11∼20
1
×
1
0
5
1×10
5
