Codeforces #250 Div1 C. The Child and Polygon

幾何パートが面倒くさすぎて間に合わなかった…。
http://codeforces.com/contest/438/problem/C

問題

Simpleな、すなわち自己交差がなく辺同士が重なったりしないN角形が与えられる。
これらを対角線で分割し、(N-2)個の三角形群にしたい。
そのような分け方はいくつあるか。

解法

この問題は2つのパートに分けられる。
1つ目はある2点間に対角線を引けるか判定、2つ目はDPである。

まず前半の対角線パート。
まじめに行うと、以下の条件を満たせば点A→点Bに対角線を引ける。

• 点A→Bの線分が他の頂点と重ならない
• 点A→Bの線分が他の(AまたはBを端点としない)辺と重ならない
• 点A→Bの線分が図形の外側を通らない。すなわちAから少しB寄りに移動した座標が図形の内部である。

今回の問題は、図形が凸とは限らず、また3つの連続した頂点が一直線に並んでたりするので非常に面倒。

最短回答を見ると、簡単な外積だけでこれらを判定しているがなぜこれで良いか不明。
恐らくこの外積判定単体ではダメで、DPパートと合わせて判断できている。

幾何パートでどの頂点間を結ぶことができるか判明したら、残りはDPパート。
点L,L+1,L+2,...R-1,R,Lを結ぶ多角形を分割する組みわせをDP[L][R]とする。答えはDP[0][N-1]である。

DP[L][R]は次の和である。

• L+2>=RならDP[L][R]=1。
• それ以外の場合：
  • 点L・L+1・Rで三角形を構築できるなら構築し、残りのDP[L+1][R]を加える。
  • L+1～R-1の間の点Pについて、点L, L+1, Pで三角形を構築できるなら構築し、DP[L+1][P]*DP[P][R]を加える。

int N;
ll X[300],Y[300];
ll mo=1000000007;

int able[201][201];
ll dpdp[201][201];
vector<pair<ll,ll> > VV;

int sgn(ll a) {
	if(a>0) return 1;
	if(a<0) return -1;
	return 0;
}

int inside(double x,double y,vector<pair<ll,ll> >& V) {
	int num=0,n=V.size(),i;
	// 右に伸ばして何回上向き・下向きと交差するか？
	// 0-out 1-in 2-border
	FOR(i,n) if(x==V[i].first && y==V[i].second) return 2; // on point
	FOR(i,n) { // on border
		double dx=V[(i+1)%n].first-V[i].first,dy=V[(i+1)%n].second-V[i].second;
		double dx2=x-V[i].first,dy2=y-V[i].second;
		if(fabs(dx*dy2-dx2*dy)>=1e-9) continue;
		if(dx!=0) {
			if(dx2/dx>=0 && dx2/dx<=1) return 1;
		}
		else if(dy2/dy>=0 && dy2/dy<=1) return 1;
	}
	
	FOR(i,n) { //cross border?
		ll x1=V[i].first,y1=V[i].second;
		ll x2=V[(i+1)%n].first,y2=V[(i+1)%n].second;
		if(y1==y2) continue;
		if(y1==y) {
			if(x1>=x && y2<y) num++; // down
		}
		else if(y2==y) {
			if(x2>=x && y1<y) num--; // up
		}
		else if(y1>y && y2<y) { //down
			double xx=x1+(x2-x1)*(double)(y-y1)/(y2-y1);
			if(xx>=x) num++;
		}
		else if(y1<y && y2>y) { //up
			double xx=x1+(x2-x1)*(double)(y-y1)/(y2-y1);
			if(xx>=x) num--;
		}
	}
	return num!=0;
}

int test(int aa,int bb) {
	if((aa+1)%N==bb || (bb+1)%N==aa) return 1;
	int i;
	FOR(i,N) if(i!=aa && i!=bb) {
		ll x1=X[i]-X[aa];
		ll y1=Y[i]-Y[aa];
		ll x2=X[bb]-X[aa];
		ll y2=Y[bb]-Y[aa];
		if(x1*y2-x2*y1!=0) continue;
		if(x2!=0) {
			double d=x1/(double)x2;
			if(d>=0 && d<=1) return 0;
		}
		if(y2!=0) {
			double d=y1/(double)y2;
			if(d>=0 && d<=1) return 0;
		}
	}
	
	FOR(i,N) {
		if(aa==i || bb==i) continue;
		if(aa==(i+1)%N || bb==(i+1)%N) continue;
		ll x1=X[(i+1)%N]-X[i];
		ll y1=Y[(i+1)%N]-Y[i];
		ll x2=X[aa]-X[i];
		ll y2=Y[aa]-Y[i];
		ll x3=X[bb]-X[i];
		ll y3=Y[bb]-Y[i];
		
		if(sgn(x2*y1-x1*y2)*sgn(x3*y1-x1*y3)>=0) continue;
		x1=X[i]-X[aa];
		y1=Y[i]-Y[aa];
		x2=X[(i+1)%N]-X[aa];
		y2=Y[(i+1)%N]-Y[aa];
		x3=X[bb]-X[aa];
		y3=Y[bb]-Y[aa];
		if(sgn(x2*y3-x3*y2)*sgn(x1*y3-x3*y1)>=0) continue;
		
		return 0;
	}
	double xx1=X[bb]-X[aa];
	double yy1=Y[bb]-Y[aa];
	double rr=sqrt(xx1*xx1+yy1*yy1);
	xx1=X[aa]+xx1/10/rr;
	yy1=Y[aa]+yy1/10/rr;
	return inside(xx1,yy1,VV)>0;
}

ll dodo(int s,int e) {
	if(dpdp[s][e]>=0) return dpdp[s][e];
	if(able[s][e]==0) return dpdp[s][e]=0;
	if(s+2>=e) return dpdp[s][e]=1;
	dpdp[s][e]=0;
	for(int x=s+1;x<e;x++) if(able[s][x] && able[x][e] && able[e][s])
		dpdp[s][e]=(dpdp[s][e] + dodo(s,x)*dodo(x,e)) % mo;
	return dpdp[s][e];
}

void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>N;
	FOR(i,N) cin>>X[i]>>Y[i];
	FOR(i,N) VV.push_back(make_pair(X[i],Y[i]));
	
	FOR(x,N) for(y=x+1;y<N;y++) able[x][y]=able[y][x]=test(x,y);
	MINUS(dpdp);
	cout << dodo(0,N-1) << endl;

}

まとめ

DPパートのコード量は大したことないが、ほんと幾何パートがめんどい。