问题描述

在笛卡尔平面上给定 $n$ 个点，需用若干边与坐标轴平行的矩形覆盖所有点。每个点至少被一个矩形覆盖，且每个矩形至少覆盖包括边界在内的两个点。矩形必须具有整数边长（即宽和高均 ≥ 1），不允许出现面积为零的退化情况。要求选择矩形使得它们的总面积最小。

输入格式

• 输入包含多个测试用例，每个用例以整数 $n$（$2 \leq n \leq 15$）开始。
• 接下来$n$ 行，每行两个整数 $x$,$y$（$-1000 \leq x, y \leq 1000$）表示点的坐标，所有点互不相同。
• 最后以一个 $0$ 表示输入结束。

输出格式

对每个测试用例，输出一行表示最小总面积。

样例输入输出

输入数据 1

2  
0 1  
1 0  
0  

输出数据 1

1  

提示
总面积为所有使用矩形的面积之和。

来源

PKU Local 2006, kicc