← 返回题目列表

Codeforces · 437/E

E. 孩子和多边形

中文机器翻译题面 查看原题

这次我们的孩子有一个简单的多边形。他必须找到将多边形分割成非退化三角形的方法数,每种方法必须满足以下要求:

- 每个三角形的每个顶点都是多边形顶点之一;
- 多边形的每一边必须恰好是一个三角形的边;
- 每两个三角形的交集面积为零,所有三角形面积之和等于多边形面积;
- 每个三角形必须完全位于多边形内部;
- 每个三角形的每条边必须恰好包含多边形的两个顶点。

下图描绘了正确分割的示例。

请帮助孩子。计算他所描述的路数模 1000000007 (109 + 7)。

输入

第一行包含一个整数 n (3 ≤ n ≤ 200) — 多边形的顶点数。然后n行,每行包含两个整数。第 i 行包含 xi, yi (|xi|, |yi| ≤ 107) — 按顺时针或逆时针顺序排列的多边形的第 i 个顶点。

保证多边形是简单的。

输出

输出模 1000000007 (109 + 7) 的路数。

示例

输入 #1

4
0 0
0 1
1 1
1 0

输出 #1

2

输入 #2

4
0 0
1 0
0 1
-1 0

输出 #2

1

输入 #3

5
0 0
1 0
1 1
0 1
-2 -1

输出 #3

3

注意

在第一个示例中,有两种可能的分裂:

在第二个示例中,只有一种可能的拆分: