円とか与えられるけど、円とかほとんど関係なくて重なる正方形の面積求めるだけの問題。
超絶嘘解法。本当は座標圧縮とかするらしい。こういうのもアリかな?
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); } }