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でいいんじゃないの」とツッコまれていた。