AOJ 1202 Mobile Phone Coverage

問題概要

重なりが許される正方形が与えられる。
実数。
最大100個。
一つ以上の正方形におおわれている部分の面積を求めよ。

解法

y座標でイベント（正方形が始まるのと終わるところ）をソートして、
イベント間にある面積について計算した。

ソース

#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<cstdio>

#define REP(i,b,n) for(int i=b;i<(int)n;i++)
#define rep(i,n)   REP(i,0,n)
#define ALL(C)     (C).begin(),(C).end()
#define FOR(it,o)  for(__typeof((o).begin()) it=(o).begin(); it!=(o).end(); ++it)

using namespace std;
const int INF = 1000000000;
const int N = 100;

double l[N], r[N];
bool now[N];
class Id{
public:
  double y;
  int id;
  bool end;
  bool operator<(const Id  &a)const{
    return y < a.y;
  }
};

double merge(){
  double rightest = -INF, leftest = -INF, ret = 0;
  vector<pair<double, double> > V;
  rep(i, N){
    if(!now[i])continue;
    V.push_back(make_pair(l[i], r[i]));
  }
  sort(ALL(V));
  FOR(it, V){
    if(rightest < it->first){
      ret += abs(rightest - leftest);
      leftest = it->first;
      rightest = it->second;
    }
    else {
      rightest = max(it->second, rightest);
    }
  }
  ret += abs(rightest - leftest);
  return ret;
}

int main(){
  int n, tc = 0;
  while(cin >> n){
    if(n == 0)break;
    tc++;
    vector<Id> V;
    rep(i, n){
      now[i] = false;
      double x, y, R;
      cin >> x >> y >> R;
      V.push_back((Id){y+R, i, true});
      V.push_back((Id){y-R, i, false});
      l[i] = x - R;
      r[i] = x + R;
    }
    sort(ALL(V));
    long double pre = V.front().y, width = 0, ans = 0;
    FOR(it, V){
      if(it->end)now[it->id] = false;
      else now[it->id] = true;
      ans += abs(pre - it->y) * width;
      pre = it->y;
      width = merge();
    }
    printf("%d %.2Lf\n",tc,ans); 
  }
  return 0;
}