#P17916. Many Convex Polygons
Many Convex Polygons
题目描述
给定一个凸多边形的 个顶点,按逆时针顺序依次为 。任意三个顶点都不共线。
对于每个 ,从这些顶点中任选 个,按它们在原多边形边界上的顺序连接,得到一个凸 边形。不同的顶点子集视为不同选法。
请对每个 ,计算所有这类凸 边形的面积之和的两倍,并对 取模。
输入格式
每个文件只有一组数据。
第一行是整数 。接下来 行,每行两个整数 ,表示对应顶点的坐标。输入顺序为逆时针顺序。
输出格式
输出 行。第 行给出 时的答案模 的结果。面积和的两倍一定是整数。
数据范围
,。
保证给出的点按顺序构成凸多边形,且任意三个点不共线。
样例
6
0 0
1 0
2 1
2 2
1 2
0 1
36
54
30
6