読者です 読者をやめる 読者になる 読者になる

AOJ Problem 1202 : Mobile Phone Coverage

404 Not Found

円とか与えられるけど、円とかほとんど関係なくて重なる正方形の面積求めるだけの問題。

超絶嘘解法。本当は座標圧縮とかするらしい。こういうのもアリかな?

x軸を細切れにして、細切れを線分として見ていろいろしたらなぜか通ってしまった。

線分の被覆"面積"?は、貪欲法でy軸の始点ソートしたりして求めた。

現在の線分の終端より始端が小さければマージして、それ以外なら今の線分確定して新しい線分に移る感じ。マージはmaxで取ってる。

/*
        Problem 1202 : Mobile Phone Coverage
        http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1202
*/
#include <iostream>
#include <vector>
#include <cstdio>
#include <complex>
#include <algorithm>
using namespace std;
double unit = 0.001; // なんか1.0/2^nよりこっちのほうが誤差減った。
typedef complex<double> P;
#define rep(i,n) for(int i=0;i<n;i++)
 
bool cmp(const pair<P,P>&a,const pair<P,P>&b){
        return a.first.imag() < b.first.imag();
}
int main(){
        int n,N=0;
        while(cin >> n && n){
                vector< pair<P,P> > data;
                double ans = 0;
                rep(i,n){
                        double a,b,r;
                        cin >> a >> b >> r;
                        data.push_back(make_pair(P(a-r,b-r),P(a+r,b+r)));
                }
                sort(data.begin(),data.end(),cmp);
                for(double x=-200;x<=400;x += unit){
                        vector< pair<double,double> > L;
                        rep(i,n){
                                if(data[i].first.real() <= x && x <= data[i].second.real()){
                                        L.push_back(make_pair(data[i].first.imag(),data[i].second.imag()));
                                }
                        }
                        if(L.size() == 0)continue;
                        double sz = 0;
                        double cs = L[0].first, ce = L[0].second;               
                        for(int i=1;i<L.size();i++){
                                if(L[i].first <= ce)ce = max(ce,L[i].second);
                                else sz += ce-cs , cs = L[i].first , ce = L[i].second;
                        }
                        sz += ce-cs;
                        ans += sz * unit;
                }
                printf("%d %.2lf\n",++N,ans);
        }
 
}