Permutation

题目描述

Bessie 在一个二维网格上有 $N$（$3\le N\le 40$）个互不相同的最喜欢的点，并且任意三点不共线。对每个 $1\le i\le N$，第 $i$ 个点由两个整数 $x_i$ 和 $y_i$ 表示（$0\le x_i,y_i\le 10^4$）。 Bessie 按如下方式在这些点之间画一些线段。 她先选择这 $N$ 个点的一个排列 $p_1,p_2,\ldots,p_N$。 她画出 $p_1$ 与 $p_2$、$p_2$ 与 $p_3$、以及 $p_3$ 与 $p_1$ 之间的线段。 接着，对每个从 $4$ 到 $N$ 的整数 $i$（按顺序），她对所有满足 $j<i$ 且线段 $p_i$ 到 $p_j$ 不与之前画出的任何线段相交（端点处相交不算）的 $j$，画出从 $p_i$ 到 $p_j$ 的线段。 Bessie 注意到对每个 $i$，她恰好画出了三条新的线段。请计算在第 1 步中她可能选择的、能满足该性质的排列数量，并对 $10^9+7$ 取模。

输入格式

第一行包含 $N$。 接下来 $N$ 行，每行包含两个用空格分隔的整数 $x_i$ 和 $y_i$。

输出格式

输出排列数量对 $10^9+7$ 取模后的结果。

4
0 0
0 4
1 1
1 2

0

4
0 0
0 4
4 0
1 1

24

5
0 0
0 4
4 0
1 1
1 2

96

提示

没有任何排列可行。 所有排列都可行。 满足该性质的一个排列是 $(0,0),(0,4),(4,0),(1,2),(1,1).$ 对于这个排列， 首先，她在 $(0,0),(0,4),$ 和 $(4,0)$ 的每一对点之间画线段。 然后她从 $(0,0),$ $(0,4),$ 和 $(4,0)$ 向 $(1,2)$ 画线段。 最后，她从 $(1,2),$ $(4,0),$ 和 $(0,0)$ 向 $(1,1)$ 画线段。 图示： 如果一个排列的前四个点在某种顺序下是 $(0,0)$、$(1,1)$、$(1,2)$ 和 $(0,4)$，则该排列不满足该性质。 评分： 测试点 1-6 满足 $N\le 8$。 测试点 7-20 没有额外限制。 题目来源：Benjamin Qi

标签: USACO|2021|Gold

来源

USACO|2021|Gold