#P6663. [2019雅礼集训]convex

    ID: 6513 传统题 2000ms 512MiB 尝试: 3 已通过: 1 难度: 8 上传者: 标签>难度分类提高+/省选-计算几何鞋带公式叉积排序与序列处理一维前缀和同向双指针枚举与搜索对称性去重模拟与实现技巧增量维护CF2400

[2019雅礼集训]convex

[2019雅礼集训]convex

题目描述

给定一个有 nn 个顶点的严格凸多边形。选择任意一条对角线,将多边形切成两部分。

若两部分面积为 S1,S2S_1,S_2,则该方案的不和谐度为 ∣S1−S2∣|S_1-S_2|。求所有对角线方案的不和谐度之和的两倍,即

2∑对角线 d∣S1(d)−S2(d)∣.2\sum_{\text{对角线 }d}|S_1(d)-S_2(d)|.

对角线连接两个不相邻的顶点,每条对角线只计一次,不包括多边形的边。因此共有 n(n−3)2\frac{n(n-3)}2 种方案。

输出答案对 109+710^9+7 取模的结果。

输入格式

从标准输入读入。

第一行一个整数 nn。

接下来 nn 行,每行两个整数 xi,yix_i,y_i,按顺时针顺序给出多边形各顶点的坐标。

输出格式

向标准输出写出一个整数,表示所求结果对 109+710^9+7 取模后的值。

样例输入 1

5
2 4
2 7
5 7
5 4
3 -2

样例输出 1

90

样例输入 2

4
-1000000000 1000000000
1000000000 1000000000
1000000000 -1000000000
-1000000000 -1000000000

样例输出 2

0

样例 3

原题的第 3 组样例见配套文件 convex/convex3.in 和 convex/convex3.ans。

数据范围

所有数据满足 4≤n≤2×1064\le n\le2\times10^6,∣xi∣,∣yi∣≤109|x_i|,|y_i|\le10^9。保证给出的多边形严格凸。

本题共 2020 个测试点,每个测试点 55 分。

测试点编号 nn 的限制
1,21,2 n=4n=4
3,43,4 n≤8n\le8
5,65,6 n≤100n\le100
7,87,8 n≤2000n\le2000
9,109,10 n≤104n\le10^4
11,12,13,1411,12,13,14 n≤105n\le10^5
15,16,1715,16,17 n≤5×105n\le5\times10^5
18,19,2018,19,20 n≤2×106n\le2\times10^6

输入规模较大,请使用合适的读入方式。