The Child and Polygon 题解
这世界这么大，遇到了这个奇奇怪怪的题。
这道题其实可以很自然的联想到卡特兰数。
在卡特兰数的计数中，有这么一个意义：\(C_n\) 表示把有 \(n+2\) 条边的凸多边形分成 \(n\) 个三角形的方案数。
利用这个意义可以得到 \(C_n\) 的另一个递推关系：
\[C_n = \sum_{k = 0}^{n - 1} {C_k C_{n-1-k}} \]而这一道题，正可以类比这个递推关系进行求解。
思路
在卡特兰数递推中，\(k\) 实际上枚举的是最后一次的分界点。也就是把整个多边形分成两部分，分别划分，再求最终方案数。
首先我们将已知的 \(n\) 个点按照顺时针方向排好序。
类比下来，我们可以設 \(f_{i, j}\) 表示由 \(i \sim j\) 这 \(j - i + 1\) 个点形成的多边形的划分数。
于是
\[f_{i, j} = \sum_{k = i}^{j} {f_{i, k} f_{k, j}} [i 可以连向 k] \]这里 \(i\) 可以连向 \(k\) 当且仅当线段 \(\vec{ij}\) 在线段 \(\vec{ik}\) 的顺时针方向。
于是本题的核心思路就已经出来了。接下来考虑实现问题。
实现
逆时针，顺时针？
我们可以通过向量叉乘的方法来判断所给的点是顺时针还是逆时针。
考虑按照所给的点的顺序计算这个多边形的面积。
枚举 \(i\) 利用 \(\vec{1i}\) 和 \(\vec{1(i+1)}\) 的叉乘，可以算出整个多边形的面积(的两倍)。
但是考虑到叉乘的正负性，如果结果为正，则所给的顺序为逆时针（因为 \(\vec{1i}\) 在 \(\vec{1(i+1)}\) 的顺时针方向）。
此时就可以搞定逆时针，顺时针的问题了。
可连？不可连？
在前面已经提到，\(i\) 可以连向 \(k\) 的条件，如何判断？
还是利用 \(\vec{ij} \times \vec{ik}\)，如果结果为正，则 \(\vec{ij}\) 在 \(\vec{ik}\) 的顺时针方向，可以连。
于是你成功的可以 \(\texttt{\colorbox{#52C41A}{\textcolor{white}{AC}}}\) 本题了。
代码
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 203, mod = 1e9 + 7;
typedef long long lint;
struct Point {
int x, y;
Point() {}
Point(int x, int y) : x(x), y(y) {}
inline lint operator * (const Point &p) {
return (1ll * x * p.y - 1ll * y * p.x);
}
inline Point operator - (const Point &p) {
return Point(x - p.x, y - p.y);
}
} p[N];
lint dp[N][N];
int main() {
cin.tie(0)->sync_with_stdio(false);
int n; cin >> n;
for (int x, y, i = 1; i <= n; ++i) {
cin >> x >> y;
p[i] = Point(x, y);
}
lint clockwiser = 0;
for (int i = 2; i < n; ++i) {
clockwiser += (p[i] - p[1]) * (p[i + 1] - p[1]);
}
if (clockwiser > 0) // if is positive, the it is counterclockwise
reverse(p + 1, p + 1 + n);
for (int i = 1; i < n; ++i)
dp[i][i + 1] = 1;
for (int len = 2; len < n; ++len) {
for (int l = 1, r = len + 1; r <= n; ++l, ++r) {
for (int k = l; k <= r; ++k) {
if ((p[r] - p[l]) * (p[k] - p[l]) > 0)
dp[l][r] = (dp[l][r] + 1ll * dp[l][k] * dp[k][r] % mod) % mod;
}
}
}
cout << dp[1][n] << '\n';
}