#P9592. 圈地

    ID: 6203 传统题 2000ms 512MiB 尝试: 2 已通过: 2 难度: 8 上传者: 标签>CF2400提高+/省选-Andrew 算法凸多边形二分查询叉积鞋带公式

圈地

题目描述

有 nn 个点在二维平面上,把他们围成一个凸包。现在可以去掉一个点,问去掉点之后能组成的最小的凸包面积是多少。

输入格式

第一行一个整数 nn。

接下来 nn 行两个整数 xi,yix_i,y_i。

输出格式

一个整数,表示最小凸包面积的两倍(可以证明答案一定是整数)。

样例

2
1 2
3 4
0
4
1 1
0 1
0 0
1 0
1
6
0 0
5 0
5 5
0 5
2 1
2 4
30

子任务

子任务编号 分值 限制 依赖
11 2323 n≤103n\leq 10^3
22 2121 所有点都在凸包上。
33 2727 不在凸包的点不超过十个。 22
44 2929 n≤105n\leq 10^5 1∼31\sim 3

对于全部数据,2≤n≤1052 \leq n \leq 10^5,$\left|x_{i}\right|,\left|y_{i}\right| \leqslant 10^{9}$。