Codeforces 420 Coder-Strike 2014 - Finals (online edition, Div. 1) E. Playing the ball

問題

座標平面上にn個の円がある。
原点から好きな方向にボールを投げる。
ボールは距離dの地点でバウンドし、2*dでバウンドし…とk*dでバウンドして無限に跳ぶ。

円の内部または周でバウンドすると1点もらえる。
もらえる得点の最大値を求めよ。

制約条件

n≦2*10^4
5≦d≦10
円の半径≦50
中心の絶対値は10万以下
原点が円の一部であることはない

方針

平面走査。
半径k*dの円と、それぞれの円が交わる場所で、
角度が小さいほうで+1, 角度が大きい方で-1をする。

これを角度の順にソートして累積和を取れば、
跳ねる回数が変化する地点それぞれで跳ねる回数がわかる。

各円で跳ねる回数は高々10回なので、交点は20個以下。
なのでこの方針で間に合う。

ソースコード

inline double fix(double a){
	if(a >= 2 * PI) a -= 2 * PI;
	if(a < 0) a += 2 * PI;
	return a;
}

int n, d;
P c[20000];
int r[20000];

int main(){
	scanf("%d%d", &n, &d);
	
	vector<pair<double, int> > event;
	
	rep(i, n){
		
		int x, y;
		scanf("%d%d%d", &x, &y, r + i);
		c[i] = P(x, y);
		
		double dist = abs(c[i]);
		double lim = dist + r[i] + EPS;
		
		for(int k = (int)ceil((dist - r[i]) / d - EPS) * d; k < lim; k += d){
			
			double t = (dist * dist + k * k - r[i] * r[i]) / 2 / dist / k;
			t = acos(t);
			
			double a = fix(arg(c[i]) - t);
			double b = fix(arg(c[i]) + t);
			
			event.pb(mp(a - EPS, 1));
			event.pb(mp(b + EPS, -1));
			if(a > b) event.pb(mp(-EPS, 1));
		}
	}
	
	//rep(i, event.size()) cerr<<event[i].first<<" "<<event[i].second<<endl;
	
	sort(all(event));
	int ans = 0;
	int cur = 0;
	
	rep(e, event.size()){
		
		cur += event[e].second;
		ans = max(ans, cur);
	}
	cout << ans << endl;
	
	return 0;
}