#P6663. [2019雅礼集训]convex
[2019雅礼集训]convex
[2019雅礼集训]convex
题目描述
给定一个有 个顶点的严格凸多边形。选择任意一条对角线,将多边形切成两部分。
若两部分面积为 ,则该方案的不和谐度为 。求所有对角线方案的不和谐度之和的两倍,即
对角线连接两个不相邻的顶点,每条对角线只计一次,不包括多边形的边。因此共有 种方案。
输出答案对 取模的结果。
输入格式
从标准输入读入。
第一行一个整数 。
接下来 行,每行两个整数 ,按顺时针顺序给出多边形各顶点的坐标。
输出格式
向标准输出写出一个整数,表示所求结果对 取模后的值。
样例输入 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。
数据范围
所有数据满足 ,。保证给出的多边形严格凸。
本题共 个测试点,每个测试点 分。
| 测试点编号 | 的限制 |
|---|---|
输入规模较大,请使用合适的读入方式。