Legend
Link ( extrm{to Codeforces})。
给定一个 (n) 个点的简单多边形，求三角剖分数目。
(3 le n le 200)。
Editorial
做题做傻了，一个显然的区间 ( m{dp}) 都没看出来。
显然设 (dp_{l,r}) 表示使用了编号 (l sim r) 的所有点进行三角剖分的方案数。
转移 (dp_{l,r} = sum_{l < k < r} dp_{l,k} imes dp{k,r})。
答案就是 (dp_{1,n})。
显然有如下情况的是不合法的状态，不能转移：
- (l o r) 的连边会穿过多边形的任何部位。
- (l o r) 的连边在多边形外部。
第一个判断就直接判断，第二个有一个神仙的判断方法。
这条边会把多边形按下标分成两个部分，如果这条边在外部并与多边形无交则一定会增加多边形的面积。
不过其实这两个有一个共同的判断方法：
在枚举 (k) 的时候看 (k) 是不是凹进去的就好了，凹进去就不合法。
Code
判断部分写得非常丑……看完题解才发现有这么简单的判断方法。
但是毕竟写都写完了，还是不改了。
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int MX = 200 + 23;
const LL MOD = 1e9 + 7;
struct VECTOR{
LL x ,y;
VECTOR(LL X = 0 ,LL Y = 0){x = X ,y = Y;}
VECTOR operator +(const VECTOR &B)const{return VECTOR(x + B.x ,y + B.y);}
VECTOR operator -(const VECTOR &B)const{return VECTOR(x - B.x ,y - B.y);}
LL operator *(const VECTOR &B)const{return x * B.y - y * B.x;}
bool operator ==(const VECTOR &B)const{return x == B.x && y == B.y;}
void Read(){cin >> x >> y;}
}P[MX];
struct SEG{
VECTOR st ,d;
SEG(){st = d = VECTOR(0 ,0);}
SEG(VECTOR __st ,VECTOR __ed){
st = __st ,d = __ed - __st;
};
void turn(){
st = st + d;
d = VECTOR(0 ,0) - d;
}
};
int sgn(LL x){
if(!x) return 0;
return x > 0 ? 1 : -1;
}
bool PingXing(VECTOR A ,VECTOR B){
return A.x * B.y - A.y * B.x == 0;
}
bool online(SEG a ,VECTOR b){
// 询问点 b 是否在 a 上（含边缘）
bool xless = b.x < a.st.x && b.x < (a.st + a.d).x;
bool xmore = b.x > a.st.x && b.x > (a.st + a.d).x;
bool yless = b.y < a.st.y && b.y < (a.st + a.d).y;
bool ymore = b.y > a.st.y && b.y > (a.st + a.d).y;
return (xless + xmore + yless + ymore) == 0;
}
int ok(SEG a ,SEG b){
// 0 绝对不行
// 1 共点
// 2 绝对可以
LL test1 = sgn(a.d * (b.st - a.st)) * sgn(a.d * (b.st + b.d - a.st));
LL test2 = sgn(b.d * (a.st - b.st)) * sgn(b.d * (a.st + a.d - b.st));
if(test1 > 0 || test2 > 0){
// 连交点都没有
return 2;
}
if(PingXing(a.d ,b.d)){
// 有交点且平行就是共线
if(online(a ,b.st) || online(a ,b.st + b.d)
|| online(b ,a.st) || online(b ,a.st + a.d)){
// 二者有交
if(sgn(a.d.x) != sgn(b.d.x) || sgn(a.d.y) != sgn(b.d.y)){
b.turn();
}
if(a.st + a.d == b.st || b.st + b.d == a.st)
return 1;
return 0;
}
return 2;
}
return (test1 <= 0 && test2 <= 0);
}
LL fad;
int n;
int check(int l ,int r){
if(l == 0 && r == 4){
puts("WTf");
}
SEG Main(P[l] ,P[r]);
LL S = fad ,s1 = 0 ,s2 = 0;
for(int i = l ; i <= r ; ++i){
if(i == r){
s1 += P[r] * P[l];
}
else{
s1 += P[i] * P[i + 1];
}
}
for(int i = r ; ; i = (i + 1) % n){
if(i == l){
s2 += P[l] * P[r];
break;
}
s2 += P[i] * P[(i + 1) % n];
}
if(abs(S) != abs(s1) + abs(s2)) return 0;
for(int i = 0 ; i < n ; ++i){
SEG t(P[i] ,P[(i + 1) % n]);
int judge = ok(Main ,t);
if(i == r && ((i + 1) % n == l)) continue;
if(judge == 0) return 0;
if(judge == 1){
if(i == l || (i + 1) % n == l || i == r || (i + 1) % n == r){
continue;
}
return 0;
}
}
return 1;
}
LL dp[MX][MX];
void test(){
int n; cin >> n;
while(n--){
int x ,y;
cin >> x >> y;
printf("(%d,%d)
" ,x ,y);
}
SEG a(VECTOR(1 ,0) ,VECTOR(-1 ,0)) ,b(VECTOR(0 ,0) ,VECTOR(1 ,0));
cout << ok(a ,b) <<endl;
return ;
}
int main(){
// test();
cin >> n;
for(int i = 0 ; i < n ; ++i){
P[i].Read();
}
for(int i = 0 ; i < n ; ++i){
fad += P[i] * P[(i + 1) % n];
}
// fad 为正数说明是顺时针给出
for(int i = 1 ; i < n ; ++i){
dp[i - 1][i] = 1;
}
for(int len = 2 ; len <= n ; ++len){
for(int st = 0 ; st + len < n ; ++st){
int ed = st + len;
if(!check(st ,ed)){
printf("[%d ,%d] is bad!
" ,st ,ed);
continue;
}
for(int k = st + 1 ; k < ed ; ++k){
dp[st][ed] = (dp[st][ed] + dp[st][k] * dp[k][ed]) % MOD;
}
printf("dp[%d][%d] = %lld
" ,st ,ed ,dp[st][ed]);
}
}
cout << dp[0][n - 1] << endl;
return 0;
}