kmjp's blog

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

TopCoder SRM 621 Div1 Easy RadioRange

SRM621に参加。
Mediumの詰めが甘くTLEしたが、Easyがかなり速く解けたのでレートは微増だった。
http://community.topcoder.com/stat?c=problem_statement&pm=13187

問題

(X[i],Y[i])を中心とした半径R[i]の円形の都市がN個ある。
ここで、原点を中心に0~Zの間の半径の円の範囲にラジオの電波を流したい。
この時、各都市の内部は全く電波が届かないか、都市内全部電波が届くのは良い半径である。
逆にどこかの都市が一部のみ電波が届くような半径は良くない半径である。

0~Zの半径のうち、良い半径の割合を示せ。

解法

各都市の原点からの距離D=√(X[i]^2+Y[i]^2に対し、悪い半径はmax(0,D-R[i])~min(Z,D+R[i])の区間である。

各都市における上記区間の和集合を取ると悪い半径を成すrangeの集合が得られるので、そのような半径を除いたものが答え。
区間の和集合を求めるために、区間の開始位置で昇順ソートし、隣接する区間と接するならマージを繰り返している。

pair<double,double> P[101];
class RadioRange {
	
	public:
	double RadiusProbability(vector <int> X, vector <int> Y, vector <int> R, int Z) {
		int N=X.size(),i;
		FOR(i,N) {
			double t=sqrt(X[i]*(ll)X[i]+Y[i]*(ll)Y[i]);
			P[i].first=max(t-R[i],0.0);
			P[i].second=min(t+R[i],(double)Z);
		}
		sort(P,P+N);
		double ng=0;
		pair<double,double> pp=make_pair(0,0);
		FOR(i,N) {
			if(P[i].first>=Z) break;
			if(P[i].first>=pp.second) {
				pp=P[i];
				ng+=P[i].second-P[i].first;
			}
			else {
				if(P[i].second>=pp.second) {
					ng+=P[i].second-pp.second;
					pp.second=P[i].second;
				}
			}
		}
		return 1-ng/Z;
	}
}

まとめ

今回割とEasyの正答率低かったので、爆速でちゃんと解けてよかった。