问题陈述
国际建筑保护协会(ICPC)和日本考古学家团体(JAG)两个组织从事遗址保护工作。 最近,在某个区域发现了很多遗迹。 两个组织决定共享遗址的保护,将部分遗址分配给 ICPC,另一部分遗址分配给 JAG。
现ICPC和JAG制定分配规则如下:
- 从北到南画一条垂直直线,避免与废墟相交。
- 位于线路以西的遗址由ICPC保存。另一方面,位于该线以东的废墟则由 JAG 保存。 (该线的东/西可能没有遗址;在这种情况下,ICPC/JAG 将不保留任何遗址。)
问题是在哪里画直线。 对于每个组织来说,保存其分配的废墟的方法就是制作一个栅栏,使得所有分配的废墟都在栅栏包围的区域内。 此外,他们应该根据预算尽量缩短围栏的长度。 如果周围区域很大,那么区域内部的维护就需要昂贵的费用。 因此,他们希望最小化总保护成本,即两道栅栏围成的面积之和。 您的任务是编写一个程序,计算由两个栅栏包围的面积的最小总和,通过绘制适当的直线得出。
输入
输入由单个测试用例组成。
$N$
$x_{1}$ $y_{1}$
...
$x_{N}$ $y_{N}$
第一行包含一个整数$N$ ($1 \le N \le 100{,}000$),这是建立的遗迹的数量。 接下来的$N$行代表废墟的位置。 其中第$i$行由两个整数$x_i$和$y_i$组成,表示第$i$个废墟的位置是从区域中某个位置向东$x_i$和向北$y_i$。 您可以对废墟做出以下假设:
- $-10^9 \le x_i, y_i \le 10^9$
- 你可以忽略废墟的大小。也就是说,你可以假设废墟是点。
- 没有一对废墟具有相同的位置。
输出
打印通过绘制适当的直线产生的最小总保存成本。 您应该将成本四舍五入到最接近的整数。
样本输入 1
8 -10 0 -10 5 -5 5 -5 0 10 0 10 -5 5 -5 5 0
样本输入 1 的输出
50
示例输入 2
5 0 0 0 1 0 2 1 0 1 1
样本输入 2 的输出
0
示例输入 3
6 1 5 1 6 0 5 0 -5 -1 -5 -1 -6
样本输入 3 的输出
6
示例输入 4
10 2 5 4 6 9 5 8 8 1 3 6 4 5 9 7 3 7 7 3 9
样本输入 4 的输出
17