さて続いてDiv2 Hard。
Div1 Mediumとどちらが難しいかな…。
http://community.topcoder.com/stat?c=problem_statement&pm=12341
円周上に並んだ杭をロープで囲い、中のペンギンを内包するような図形を作ったとき、その面積が最少となるものを求める。
まず、杭の間でロープを張れるかどうかを判定する。
2つの杭の間にロープが張れる場合、全ペンギンがロープの同じ側(ここでは左側)にいればOK。
終了後のChatではconvex hullがいいのかとか言っているが、考えたら全ペンギンを囲いたいのであってDiv1 Easyの様に辺の交差を気にしているわけでないのでこれで良い。
杭をP個、ペンギンをN体とするとこの処理はO(P^2*N)だけどP<=222、N<=50なので何とか処理できる。
ここからはもうペンギンは関係ない。
張れるロープだけを使って図形を作り、その面積を最小化する。
この処理は、始点を1個選び、そこから反時計周りにX個先の杭を選ぶ際に1~X個手前の杭からロープを張った場合に面積が最少になるかDPしていく。
始点の選び方がP通り、1回のDPがO(P^2)なので合わせてO(P^3)だけど、500ms程度で終わるようだ。
class FencingPenguinsEasy { public: int ok[250][250]; ll R; int NP; vector< int > hull, X, Y; int right(int f,int t) { int i; double PI = atan(1)*4; double fx = R*cos(2*PI*(f/(double)NP)); double fy = R*sin(2*PI*(f/(double)NP)); double tx = R*cos(2*PI*(t/(double)NP)); double ty = R*sin(2*PI*(t/(double)NP)); FOR(i,X.size()) if((X[i]-fx)*(ty-fy)-(Y[i]-fy)*(tx-fx)>0) return 0; return 1; } double minarea(int s) { int x,y; double area[300]; area[s]=0; for(x=1;x<=NP;x++) { area[(s+x)%NP]=1e30; if(x==NP) area[s]=1e30; for(y=1;y<=x;y++) { int c = (s+x)%NP, p=(s+x-y)%NP; if(!ok[p][c]) continue; area[c] = min(area[c], area[p] + R*R*sin(2*atan(1)*4*(y%NP)/NP)/2.0); } } return area[s]; } double calculateMinArea(int np, int radius, vector <int> X_, vector <int> Y_) { int i,x,y; R=radius; NP=np; X=X_; Y=Y_; FOR(x,NP) FOR(y,NP) if(x!=y) ok[x][y]=right(x,y); double mi = 1e30; FOR(x,NP) mi = min(mi, minarea(x)); if(mi>=1e29) return -1; return mi; } };
まとめ
コード自体は思ったほど複雑にならなかった。
Div2 Mediumもそうだけど、円形の処理はなかなかに面倒だな。