TopCoder SRM 621 Div1 Easy RadioRange

概要

(0,0)から半径r (0\lt r\lt z)の電波を飛ばす.
n個の街があり,i個目は中心(X_i,Y_i)で半径R_iの円形である.
すべての街について電波が全く届かないか完全に届くかのどちらかであるようなzの範囲の割合を求めよ.

解法

余事象を考えると,街iに対し良くない範囲は[max(0,sqrt(X_i^2+Y_i^2)-R_i,min(sqrt(X_i^2+Y_i^2)*R_i,z)]である.
これを各街についてとってそれらをマージし,割合を求めれば良い.

ソースコード

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define FOR(i,n,m) for(int i=(n);i<(m);i++)
#define REP(i,n) FOR(i,0,n)
#define REPR(i,n) for(int i=(n);i>=0;i--)
#define all(vec) vec.begin(),vec.end()
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using P=pair<int,int>;
using PP=pair<int,P>;
using Pl=pair<ll,ll>;
using PPl=pair<ll,Pl>;
using vs=vector<string>;
#define fi first
#define se second
#define pb push_back
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}
template<class T>bool chmin(T &a,const T &b){if(a>b){a=b;return true;}return false;}
const ll MOD=1000000007LL;
const int INF=1<<30;
const ll LINF=1LL<<60;
class RadioRange{
public:
    double dist(double x,double y){
        return sqrt(x*x+y*y);
    }
    double RadiusProbability(vi x,vi y,vi r,int z){
        using Pd=pair<double,double>;
        int n=x.size();
        vector<Pd> vec;
        REP(i,n){
            if(dist(x[i],y[i])-r[i]>z){
                continue;
            }
            vec.pb(Pd(max(0.0,dist(x[i],y[i])-r[i]),min(1.0*z,dist(x[i],y[i])+r[i])));
        }
        while(1){
            bool f=false;
            vector<Pd> t;
            sort(all(vec));
            int m=vec.size();
            REP(i,m){
                int r=i;
                double ma=vec[i].se;
                while(r+1<m&&vec[r+1].fi<vec[r].se){
                    r++;
                    f=true;
                    chmax(ma,vec[r].se);
                }
                t.pb(Pd(vec[i].fi,ma));
                i=r;
            }
            vec=t;
            if(!f){
                break;
            }
        }
        double res=0.0;
        REP(i,vec.size()){
            res+=vec[i].se-vec[i].fi;
        }
        return 1.0-res/z;
    }
};