TopCoder, SRM 621, Division 1, Level 1 : RadioRange

問題文

http://community.topcoder.com/stat?c=problem_statement&pm=13187&rd=15854

問題概要

　二次元平面上にいくつかの円があり、i 番目の円の中心座標は ( X[ i ], Y[ i ] ) 、半径は R[ i ] である。
　これらの円とは別に、原点を中心とする円を考える。この円の半径は [ 0, Z ] の範囲からランダムに選ばれる。この円が good であるとは、その他の円を部分的に被覆しない（＝その他の円は全て、この円に完全に含まれるか完全に含まれないかのいずれかである）ことを言い、それ以外は bad である。
　原点にある円が good となる確率を求めよ。

解法

　まず、一つの円だけが与えられる場合について考えてみます。円の中心座標と原点の距離を d 、円の半径を r とします。この場合、（原点の）円が good となる半径は、d - r 以下か d + r 以上の場合であり、[ d - r, d + r ] に入る場合は bad となります。この区間と [ 0, Z ] との共通部分の長さを [ 0, Z ] の長さ（＝ Z ）で割った値が bad になる確率であり、これを p とすれば good となるのはこの余事象であるので 1 - p です。
　円が複数の場合についても同様に bad になる区間を考えます。円が複数の場合区間が重なってしまう場合があるので、単純な長さの和ではなく一つ以上の区間に被覆されている区間の長さを求める必要があります。これは、いもす法で区間を足し合わせて、1 以上となっている部分を数えることで実現できます。今回の問題では考慮する値が広く、また実数値をとるので、配列を使う普通の実装の代わりに std::map を使います。
　区間の長さを求めた後、それを L とすれば 1 - L / Z が答えです。

コード

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define FOR( e, c ) for ( auto &e : c )

#define fst first
#define snd second

class RadioRange
{
public:
	double RadiusProbability( vector <int> X, vector <int> Y, vector <int> R, int Z )
	{
		const int N = X.size();

		map<double,int> count;
		REP( i, 0, N )
		{
			const double d = hypot( X[i], Y[i] );
			count[ clipping( Z, d - R[i] ) ]++;
			count[ clipping( Z, d + R[i] ) ]--;
		}

		double res = 0, prev = 0;
		int c = 0;
		
		FOR( p, count )
		{
			if ( c == 0 )
			{
				prev = p.fst;
			}
			c += p.snd;
			if ( c == 0 )
			{
				res += p.fst - prev;
			}
		}

		return 1 - res / Z;
	}

	double clipping( const double Z, const double a )
	{
		return max( 0., min( a, Z ) );
	}
};