1202 Mobile Phone Coverage
#include<stdio.h>
#include<vector>
#include <algorithm>
#include <set>
int IN=1;
int OUT=-1;
struct point{
double lx,y,rx;
int inOut;
bool operator<(const point& p)const{
if(y!=p.y)return y<p.y;
return inOut>p.inOut;//inが優先
}
};
int no=1;
void calc(int n){
double x,y,r;
point p;
std::vector<point> points;
std::set<double> xset;
for(int i=0;i<n;i++){
scanf("%lf %lf %lf",&x,&y,&r);
//下
p.lx=x-r;
p.rx=x+r;
p.y=y-r;
p.inOut=IN;
points.push_back(p);
p.y=y+r;
p.inOut=OUT;
points.push_back(p);
xset.insert(x-r);
xset.insert(x+r);
}
std::sort(points.begin(),points.end());
double hLen,ans=0,dx;
int inCount;
bool nextIn;
std::set<double>::iterator it=xset.begin();
x=(*it);
while(it!=xset.end()){
//x座標の小さい方から切り分けていく
it++;
if(it==xset.end())break;
dx=(*it)-x;
x=(*it);
inCount=0;
hLen=0.0;
nextIn=true;
//printf("%lf>",x);
for(int lp=0;lp<points.size();lp++){
p=points[lp];
//printf("(%.2lf %.2lf)",x,p.rx);
//切り分けた範囲をy座標の小さい方から走査してエリアに入る入らないを調べてく
if(p.lx<x&&x<=p.rx){
if(nextIn==true){
inCount=1;
y=p.y;
//printf("<%.2lf> ",p.y);
nextIn=false;
}else{
inCount+=p.inOut;
if(inCount==0){
nextIn=true;
//printf("(p.y=%.2lf,%.2lf)",p.y,y);
hLen+=p.y-y;
}
//printf(" /%d %d/ ",p.inOut,inCount);
}
}
}
ans+=dx*hLen;
//printf("(h=%lf dx=%lf x=%lf %lf)\n",hLen,dx,x,dx*hLen);
}
printf("%d %.2lf\n",no,ans);
no++;
}
int main(){
int n;
while(1){
scanf("%d",&n);
if(n==0)break;
calc(n);
}
}
最終更新:2012年07月05日 16:36