#P18548. Almost Convex 2
Almost Convex 2
Almost Convex 2
这又是一个关于小青鱼的朋友 Kevin 的故事。
Kevin 是国际凸多边形锦标赛(International Convex Polygon Championship,ICPC)的总裁判长。他为比赛出了一道几何题,但由于缺乏计算几何经验,没能为测试数据生成正确的凸多边形,因此十分沮丧。
小青鱼安慰他说:“虽然你生成的不是凸多边形,但可以把它称为几乎凸多边形!”

给定平面点集 S,其中至少有3个点,任意两点不重合、任意三点不共线。小青鱼称多边形 P 为几乎凸多边形,当且仅当:
- P 是简单多边形:各顶点互不相同;任意两条边不能相交或接触,唯一的例外是相邻两边可以在共同端点处接触。
- P 的所有顶点均属于 S,且 S 中的所有点均在 P 的内部或边界上。
令 U 为所有几乎凸多边形构成的集合。可以证明 U 有限且非空。因此,U 中存在顶点数最少的多边形 R。这里 |R| 表示 R 的顶点数。
Kevin 和小青鱼想知道:有多少个多边形 Q∈U 满足 |Q|≤|R|+2?请计算这个数量。
这里统计的是几何多边形本身;同一个顶点循环更换起点或反向描述,不会产生另一个多边形。
输入格式
第一行一个整数 n(3≤n≤500),表示 S 中的点数。
接下来 n 行,第 i 行两个整数 x_i,y_i(−10000≤x_i,y_i≤10000),表示一个点。
保证任意两点不重合、任意三点不共线。点的输入顺序没有特殊保证。输入只有这一组数据。
输出格式
输出一行一个整数,表示满足条件的多边形 Q 的数量。答案不取模。
原样例1
7
0 2
1 0
1 3
2 5
3 0
3 3
4 2
26
原样例2
5
4 0
0 0
2 1
3 3
3 1
13
原样例3
3
0 0
3 0
0 3
1