SRM621 div1 easy RadioRange

考えたこと

中心が(0, 0)で半径がrの円と中心が(X, Y)で半径がRの円が共有する部分を持つ条件について考える。半径rが （2円が外接する半径r_1）<= r < （2円が内接する半径r_2）の条件を満たすときと言い換えられる。
r_1 = max(0, sqrt(XX+YY)) (円の中に(0, 0)が存在する場合0)
r_2 = min(Z, sqrt(XX+YY))
とできるのでそれぞれの円について[r_1, r_2]を求めこの範囲の和集合を取ることで共有部分を持つ区間を求めることができる。

和集合を取る部分をバグらせまくったりオーバーフローさせたりいろいろ反省。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)

pair<double, double> p[105];
class RadioRange {
  public:
  double RadiusProbability(vector <int> X, vector <int> Y, vector <int> R, int Z)
  {
    int n = X.size();
    REP(i, n) {
      double l = sqrt((double)X[i]*X[i]+(double)Y[i]*Y[i]);
      p[i] = {max(l-R[i], 0.0), min(l+R[i], (double)Z)};
    }
    sort(p, p+n);
    double sum = 0;
    double l = 0, r = 0;
    REP(i, n) {
      if(p[i].first >= Z) break;
      if(p[i].first>=r) {
        l = p[i].first, r = p[i].second;
        sum += r-l;
      } else if(p[i].second>=r) {
        sum += p[i].second - r;
        r = p[i].second;
      }
    }

    return 1-sum/Z;
  }
};