#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