「AOJ1200～1210」の編集履歴（バックアップ）一覧に戻る

AOJ1200～1210 - (2012/07/05 (木) 16:36:01) のソース

*1202　Mobile Phone Coverage
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1202
簡単な問題。
左端から少しずつ走査して足しこんでいけば解ける。
範囲境界線上のｘ座標を全て網羅しｙ軸と平行に画面を切り取って後は少しずつ面積を足していくだけである。
もう少し賢い方法もある気はするが自前で思いついた方法を優先。
解答番号をprintfし忘れて一度不正解を食らったのはここだけの秘密。
私の場合問題はきちんと解けてるが最後のprintfで書き忘れで不正解というパタンが多い。
多分問題が解けて油断してるんだと思う。

 #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);
			//切り分けた範囲をｙ座標の小さい方から走査してエリアに入る入らないを調べてく
			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);
	}
 }