8279: Permutation
内存限制：128 MB
时间限制：1 S
标准输入输出
题目类型：传统
评测方式：文本比较
上传者：
提交：1
通过：1
题目描述
Bessie 在二维平面上有 $N$ 个最爱的不同的点，其中任意三点均不共线。对于每一个 $1\le i\le N$，第 $i$ 个点可以用两个整数 $x_i$ 和 $y_i$ 表示。
Bessie 按如下方式在这些点之间画一些线段：
- 1. 她选择这 $N$ 个点的某个排列 $p_1,p_2,\dots,p_N$ 。
- 2. 她在点 $p_1$ 和 $p_2$ 、$p_2$ 和 $p_3$、$p_3$ 和 $p_1$ 之间画上线段。
- 3. 然后依次对于从 $4$ 到 $N$ 的每个整数 $i$，对于所有 $j<i$，她从 $p_i$ 到 $p_j$ 画上一条线段，只要这条线段不与任何已经画上的线段相交（端点位置相交除外）。
Bessie 注意到对于每一个 $i$ ，她都画上了恰好三条新的线段。计算 Bessie 在第 $1$ 步可以选择的满足上述性质的排列的数量，结果对 $10^9+7$ 取模。
## 输入格式
输入的第一行包含 $N$。
以下 $N$ 行，每行包含两个空格分隔的整数 $x_i$ 和 $y_i$。
## 输出格式
输出一行一个整数表示方案数对 $10^9+7$ 取模后的结果。
$3\le N \le 40$，$0\le x_i,y_i \le 10^4$
Bessie has N (3≤N≤40) favorite distinct points on a 2D grid, no three of which are collinear. For each 1≤i≤N, the i-th point is denoted by two integers xi and yi (0≤xi,yi≤104).
Bessie 按如下方式在这些点之间画一些线段：
- 1. 她选择这 $N$ 个点的某个排列 $p_1,p_2,\dots,p_N$ 。
- 2. 她在点 $p_1$ 和 $p_2$ 、$p_2$ 和 $p_3$、$p_3$ 和 $p_1$ 之间画上线段。
- 3. 然后依次对于从 $4$ 到 $N$ 的每个整数 $i$，对于所有 $j<i$，她从 $p_i$ 到 $p_j$ 画上一条线段，只要这条线段不与任何已经画上的线段相交（端点位置相交除外）。
Bessie 注意到对于每一个 $i$ ，她都画上了恰好三条新的线段。计算 Bessie 在第 $1$ 步可以选择的满足上述性质的排列的数量，结果对 $10^9+7$ 取模。
## 输入格式
输入的第一行包含 $N$。
以下 $N$ 行，每行包含两个空格分隔的整数 $x_i$ 和 $y_i$。
## 输出格式
输出一行一个整数表示方案数对 $10^9+7$ 取模后的结果。
$3\le N \le 40$，$0\le x_i,y_i \le 10^4$
Bessie has N (3≤N≤40) favorite distinct points on a 2D grid, no three of which are collinear. For each 1≤i≤N, the i-th point is denoted by two integers xi and yi (0≤xi,yi≤104).
Bessie draws some segments between the points as follows.
- She chooses some permutation p1,p2,…,pN of the N points.
- She draws segments between p1 and p2, p2 and p3, and p3 and p1.
- Then for each integer ii from 4 to N in order, she draws a line segment from pi to pj for all j<i such that the segment does not intersect any previously drawn segments (aside from at endpoints).
Bessie notices that for each ii, she drew exactly three new segments. Compute the number of permutations Bessie could have chosen on step 1 that would satisfy this property, modulo 109+7.
输入格式
The first line contains N.
Followed by N lines, each containing two space-separated integers xi and yi.
输出格式
The number of permutations modulo 109+7.
输入样例 复制
5
0 0
0 4
4 0
1 1
1 2输出样例 复制
96数据范围与提示
One permutation that satisfies the property is (0,0),(0,4),(4,0),(1,2),(1,1). For this permutation,
- First, she draws segments between every pair of (0,0),(0,4), and (4,0).
- Then she draws segments from (0,0), (0,4), and (4,0) to (1,2).
- Finally, she draws segments from (1,2), (4,0), and (0,0) to (1,1).
Diagram:
The permutation does not satisfy the property if its first four points are (0,0), (1,1), (1,2), and (0,4) in some order.
SCORING:
- Test cases 1-6 satisfy N≤8.
- Test cases 7-20 satisfy no additional constraints.