Codeforces #357 Div2 E. Runaway to a Shadow

しょうもないミスしたけど解けて良かった。ミスしてなくても順位変わらないし…。
http://codeforces.com/contest/681/problem/E

問題

座標(X0,Y0)にいるゴキブリが、360度ランダムに等確率で速度vで時間Tの間移動する。
ここでN個の円の中心(X,Y)及び半径Rが与えられる。

時間T以内に、どこかの円の内部に到達する確率を求めよ。

解法

まず座標全体を(-X0,-Y0)ずらし、ゴキブリの初期位置を(0,0)にしよう。
原点がすでにどこかの円に含まれるなら、解は1。

そうでないなら、各円に対してゴキブリが時刻T以内に入るような角度の範囲[θ1,θ2]を求めよう。
各円に対する範囲の和集合を取り、360度のうちどれだけをカバーするか考えるとよい。

D := 原点から(X,Y)までの距離
θ := 原点から(X,Y)への偏角
r := v*T
R := 入力のR
としたとき、[θ1,θ2]を考える。
まずr ＜ D-Rならそもそもゴキブリは円に到達できないので、条件を満たす範囲はない。
そうでない場合、円のどこかには到達可能である。

当然円に最短で向かうには、角度θで行くのが良い。
そこからどれだけ角度がずれても距離rで円に到達できるか、最大値δを求めよう。[θ-δ, θ+δ]が求めたい範囲となる。

円の接線方向に向かう場合δが最大となる。ただしこの場合はr^2+R^2≧D^2を満たすようなrでないと、接線方向に距離r移動して円にたどり着くことができない。
rが√(D^2-R^2)未満の場合、原点からの距離rでちょうど円周部に到達する角度が最大値δとなる。
この場合、予言定理よりD^2+r^2-2Dr cosδ = R^2となるのでacosを使えばδを求められる。

地味にv*Tが極端に大きかったり、ちょこちょこlong longに収まらない数字がでるので注意。

ll X0,Y0,V,T;
int N;
ll X,Y,R;
vector<pair<double,double>> range;

void solve() {
	int i,j,k,l,r,x,y; string s;
	double pi=atan(1)*4;
	
	cin>>X0>>Y0>>V>>T;
	V=min(V*T,6*1000000000LL);
	
	cin>>N;
	FOR(i,N) {
		cin>>X>>Y>>R;
		X-=X0;
		Y-=Y0;
		if(X*X+Y*Y<=R*R) return _P("1\n");
		if(R==0) continue;
		double D=sqrt(X*X+Y*Y);
		if(V<D-R) continue;
		double at=atan2(Y,X);
		double dif=asin(R/D);
		if((double)V*V+(double)R*R<D*D) {
			double A=(double)V*V+D*D-(double)R*R;
			A /= 2*V*D;
			dif = acos(A);
		}
		if(at+dif>pi) {
			range.push_back({at-dif,pi});
			range.push_back({-pi,at+dif-2*pi});
		}
		else if(at-dif<-pi) {
			range.push_back({-pi,at+dif});
			range.push_back({at-dif+2*pi,pi});
			
		}
		else {
			range.push_back({at-dif,at+dif});
		}
	}
	
	sort(ALL(range));
	double pre=-pi;
	double tot=0;
	FORR(r,range) {
		pre=max(pre,r.first);
		if(r.second-pre>0) tot+=r.second-pre;
		pre=max(pre,r.second);
	}
	_P("%.12lf\n",tot/(2*pi));
	
}

まとめ

これオーバーフローひっかけ要らないと思うんだけどなぁ。