kmjp's blog

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

Codeforces #339 Div1. A. Peter and Snow Blower

Bをしょうもないミスして、レート大幅上昇のチャンスが微増になってしまった。
http://codeforces.com/contest/613/problem/A

問題

多角形を構成する頂点の座標と、多角形外にある中心点の位置が与えられる。
多角形を中心点を中心に回転させたとき、多角形が通過する領域の面積を求めよ。

解法

多角形において、中心点から最も遠い点が(回転により)生成する円の面積から、最も近い点が生成する面積を引いたものが答え。
前者は、多角形の頂点のうち最遠点を選べばよい。
後者は、多角形における最も近い点は多角形の頂点とは限らず、辺の途中にある場合もある。

辺を成す線分のうち、中心点に最も近い位置への距離は、二分探索もしくはベクトル演算で求めよう。
以下は後者。

int N;
ll X[101010],Y[101010],PX,PY;
double ma,mi;


void solve() {
	int i,j,k,l,x,y; string s;
	
	mi=1e12;
	cin>>N>>PX>>PY;
	FOR(i,N) {
		cin>>X[i]>>Y[i];
		X[i]-=PX;
		Y[i]-=PY;
		ll r=X[i]*X[i]+Y[i]*Y[i];
		ma=max(ma,(double)r);
		mi=min(mi,(double)r);
	}
	X[N]=X[0];
	Y[N]=Y[0];
	
	FOR(i,N) {
		double dx=X[i+1]-X[i];
		double dy=Y[i+1]-Y[i];
		double dx2=-X[i];
		double dy2=-Y[i];
		double rad=sqrt(dx*dx+dy*dy);
		dx/=rad;
		dy/=rad;
		
		double sp=dx*dx2+dy*dy2;
		if(0<=sp&&sp<=rad) {
			double tx=X[i]+sp*dx;
			double ty=Y[i]+sp*dy;
			double rr=tx*tx+ty*ty;
			ma=max(ma,(double)rr);
			mi=min(mi,(double)rr);
		}
	}
	_P("%.12lf\n",(ma-mi)*atan(1)*4);
	
}

まとめ

典型だけど面倒な(であまり面白くない)問題。
Codeforcesのサイト上でも「この問題こそEducational Roundでいいんじゃないの」とツッコまれていた。