幾何パートが面倒くさすぎて間に合わなかった…。
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パートのコード量は大したことないが、ほんと幾何パートがめんどい。