#P18254. Concave Hull
Concave Hull
Concave Hull
平面上有 个点,第 个点的坐标为 。
本题称一个多边形为凹包(Concave Hull),当且仅当它满足以下全部条件:
- 它是简单多边形,即边界没有自交;
- 它的顶点集合是给定 个点的一个非空子集;
- 给定的所有 个点都在多边形内部或边界上;
- 恰好一个内角大于 ,其他所有内角都严格小于 。
求给定点集的所有凹包的面积之和的两倍。答案可能很大,请输出其对 取模的结果。
同一个几何多边形不会因为选择不同起点或反向遍历而被重复计算。不存在凹包时,面积之和为 。
输入格式
第一行包含一个整数 ,表示点数。
接下来 行,第 行包含两个整数 ,表示第 个点的坐标。
输出格式
输出一行一个整数,表示所有凹包的面积之和的两倍,对 取模。
数据范围
- ;
- ;
- 所有点两两不同,且任意三个点都不共线。
输入只有一组数据。
样例 1
4
0 0
2 0
1 2
1 1
8
样例 2
15
3442 3341
3136 3120
3228 3113
3143 2981
3050 3052
2970 2973
2964 3011
2921 2927
2844 2715
2655 2661
2666 2637
2755 2731
2657 2684
2662 2629
2542 2508
23993862
样例说明
第一个样例共有三个凹包,如原题下图所示。

它们的面积分别为 、 和 ,总面积为 ,所以输出 。