TopCoder SRM 621 Div1 Easy RadioRange [1人競技プログラミング Advent Calendar 2016 20日目]

ここまで続けてきて初の275点問題。今まで全部250点問題でした。
この記事は1人競技プログラミング Advent Calendar 2016 20日目の記事です。

問題概要：
TopCoder Statistics - Problem Statement
N(1<=N<=100)個の町があり、i番目の町の中心が(X[i],Y[i])(-10⁹ <= X[i],Y[i] <= 10⁹)で与えられる。
i番目の町の範囲はi番目の町の中心から半径Ri以内のエリアで与えられる。

座標(0,0)にラジオ塔を建て、半径Z(1<=Z<=10⁹)以内のエリアにラジオが届く。
全てのそれぞれの町において、ラジオが町の全てのエリアに届かないか、全てのエリアに届いている状態が良い状態である。

半径Zの内、良い状態の部分の割合を誤差1^-6以内で答えよ。

解いた方法：
全ての町において、悪い状態になる最小値と最大値を列挙する。
町の中心とラジオ塔の中心(0,0)で線を引き、町側の円と線が隣接している部分が最小値と最大値になる。

後は悪い部分が重複しているエリアをうまく計算して悪い部分がどのぐらいあるのかの合計値を求めれば答えが出てくる。
オーバーフローには要注意。(サンプルが優しいので救ってくれる)

#include<bits/stdc++.h>

#define MP make_pair
#define PB push_back
#define ALL(x) (x).begin(),(x).end()
#define REP(i,n) for(int i=0;i<(n);i++)
#define REP1(i,n) for(int i=1;i<(n);i++)
#define REP2(i,d,n) for(int i=(d);i<(n);i++)
#define RREP(i,n) for(int i=(n);i>=0;i--)
#define CLR(a)      memset((a),0,sizeof(a))
#define MCLR(a)     memset((a),-1,sizeof(a))
#define RANGE(x,y,maxX,maxY) (0 <= (x) && 0 <= (y) && (x) < (maxX) && (y) < (maxY))

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef vector<LL> VLL;
typedef pair<int,int> PII;

const int INF = 0x3f3f3f3f;
const LL INFL = 0x3f3f3f3f3f3f3f3fLL;
const double EPS = 1e-9;

const int DX[]={1,0,-1,0},DY[]={0,-1,0,1};

class RadioRange {
    public:
    vector<int> X;
    vector<int> Y;
    vector<int> R;
    int Z;
    double RadiusProbability(vector<int> _XX, vector<int> _YY, vector<int> _RR, int _ZZ) {
        X = _XX, Y = _YY, R = _RR, Z = _ZZ;

        vector<pair<double, double> > lens;
        bool used[100];
        REP(i, X.size()){
            used[i] = false;
            double dis = sqrt((double)X[i]*X[i] + (double)Y[i]*Y[i]);
            double mn = max(0.0, dis - R[i]);
            double mx = min((double)Z, dis + R[i]);
            lens.PB(MP(mn, mx));
        }

        sort(ALL(lens));
        double del_size = 0.0;
        REP(i, lens.size()){
            if(used[i]) continue;

            used[i] = true;
            REP2(j, i+1, lens.size()){
                if(lens[j].first <= lens[i].second){
                    used[j] = true;
                    lens[i].second = max(lens[i].second, lens[j].second);
                }
            }
            if((double)Z <= lens[i].first) continue;
            del_size += lens[i].second - lens[i].first;
        }

        return (double)(Z - del_size) / Z;
    }
};