#1182. 凸包

内存限制:512 MiB 时间限制:500 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: q3540555

题目描述

有一个 个点的凸包,现在你想沿某个对角线将凸包切成两半(共有 种选择)。

你定义一种方案的不和谐度为切成的两半的面积之差的绝对值,现在你想知道所有方案的不和谐度之和乘以 的结果。 由于答案可能比较大,你只需要输出其对 取模的结果。

输入格式

第一行一个整数 . 接下来 行,每行两个整数 ,按顺时针顺序给出凸包上每个点的坐标。

输出格式

输出一行一个整数表示答案。

样例

5
2 4
2 7
5 7
5 4 
3 -2
90
4
-1000000000 1000000000 
1000000000 1000000000 
1000000000 -1000000000 
-1000000000 -1000000000
0

数据范围与提示

保证给出的多边形严格为凸包.