kmjp's blog

競技プログラミング参加記です

TopCoder SRM 566 Div2 Hard FencingPenguinsEasy

さて続いて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もそうだけど、円形の処理はなかなかに面倒だな。