RadioRange.cpp

/*

街を原点を中心に回転して角度を揃えても結果は変わらない。
街が何個重なっているかを更新しながら、街が重なっていない部分の長さを足していけば
良い。[0, Z]以外の部分にも街があると考えるとプログラムが楽。

*/

#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <cmath>
using namespace std;

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

    vector<pair<double, int> > V;
    for (int i=0; i<n; i++)
    {
        double r = hypot(X[i], Y[i]);
        V.push_back(make_pair(r-R[i], +1));
        V.push_back(make_pair(r+R[i], -1));
    }
    V.push_back(make_pair(-1e20, +1));
    V.push_back(make_pair(0.0, -1));
    V.push_back(make_pair((double)Z, +1));
    V.push_back(make_pair(+1e20, -1));

    sort(V.begin(), V.end());
    int s = 1;
    double ans = 0;

    for (int i=1; i<(int)V.size(); i++)
    {
        if (s==0)
            ans += V[i].first - V[i-1].first;
        s += V[i].second;
    }

    return ans/Z;
}};