← 返回题目列表

AtCoder · icpc2016autumn_g

G. 分享遗址保护

中文机器翻译题面 查看原题

问题陈述

国际建筑保护协会(ICPC)和日本考古学家团体(JAG)两个组织从事遗址保护工作。 最近,在某个区域发现了很多遗迹。 两个组织决定共享遗址的保护,将部分遗址分配给 ICPC,另一部分遗址分配给 JAG。

现ICPC和JAG制定分配规则如下:

  1. 从北到南画一条垂直直线,避免与废墟相交。
  2. 位于线路以西的遗址由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