OpenJudge

6:矩形覆盖

总时间限制:
3000ms
内存限制:
65536kB
描述
在平面上给出了n个点,现在需要用一些平行于坐标轴的矩形把这些点覆盖住。每个点都需要被覆盖,而且可以被覆盖多次。每个矩形都至少要覆盖两个点,而且处于矩形边界上的点也算作被矩形覆盖。注意:矩形的长宽都必须是正整数,也就是说矩形不能退化为线段或者点。

现在的问题是:怎样选择矩形,才能够使矩形的总面积最小。
输入
输入包括多组测试数据。每组测试数据的第一行给出n (2 <= n <= 15),表示平面上的点数。后面的n行,每行上包括两个整数x, y (-1000 <= x, y <= 1000),给出一个点在平面上的x坐标和y坐标。输入数据保证:这n个点在平面上的位置各不相同。

最后一组测试数据中n = 0,表示输入的结束,这组数据不用处理。
输出
对每一组测试数据,输出一行,包括一个正整数,给出矩形的最小总面积。
样例输入
2
0 1
1 0
0
样例输出
1
提示
矩形的总面积指的是所有矩形的面积直接相加的结果
全局题号
1793
添加于
2012-09-11
提交次数
11
尝试人数
4
通过人数
1