Problem 1202 : Mobile Phone Coverage

問題概要

アンテナは、自身の座標を(x,y)とすれば左上(x-r,y-r)右上(x+r,y+r)の正方形の範囲をカバーする。
（ただしrはアンテナ毎に異なる値である。）

アンテナの各座標および半径rが与えられたとき、
最低一つのアンテナによりカバーされる領域の面積を求めよ。

解法

座標圧縮する。
すると、領域は100x100のグリッド上の正方形で表される。
よってそれぞれのアンテナを塗りつぶして、最後に塗りつぶされたグリッドの面積を数えればよい。

ソースコード

int n,X1[100],X2[100],Y1[100],Y2[100];
int nx,ny;
double xv[200],yv[200];
bool v[200][200];

int main()
{
	int cs=1;
	while(scanf("%d",&n),n)
	{
		double x[200],y[200],r[200];
		rep(i,n)
		{
			scanf("%lf%lf%lf",x+i,y+i,r+i);
			xv[i*2]=x[i]-r[i]; xv[i*2+1]=x[i]+r[i];
			yv[i*2]=y[i]-r[i]; yv[i*2+1]=y[i]+r[i];
		}
		rep(i,2*n)x[i]=xv[i],y[i]=yv[i];
		sort(xv,xv+2*n); sort(yv,yv+2*n);
		nx=unique(xv,xv+2*n)-xv; ny=unique(yv,yv+2*n)-yv;
		rep(i,n)
		{
			X1[i]=lower_bound(xv,xv+nx,x[i*2])-xv;
			X2[i]=lower_bound(xv,xv+nx,x[i*2+1])-xv;
			Y1[i]=lower_bound(yv,yv+ny,y[i*2])-yv;
			Y2[i]=lower_bound(yv,yv+ny,y[i*2+1])-yv;
		}
		
		double ans=0;
		rep(i,ny)rep(j,nx)v[i][j]=0;
		rep(i,n)
		{
			for(int y=Y1[i];y<Y2[i];y++)for(int x=X1[i];x<X2[i];x++)
			if(!v[y][x])
			{
				ans+=(yv[y+1]-yv[y])*(xv[x+1]-xv[x]);
				v[y][x]=1;
			}
		}
		printf("%d %.2f\n",cs++,ans);
	}
	return 0;
}