PKU演習問メモ(8/1)

体調悪い。

No.	問題名	問題の種類および解法	難易度
1151	Atlantis	座標圧縮	★★★☆☆

1151 Atlantis

問題概要

n個の長方形が、その4頂点の座標(x1,y1,x2,y2)により与えられる。
このとき、全ての長方形のを重ねた図形の面積を求めよ。

n≦100である。

解法

包除原理だと思って放置していた問題。実は座標圧縮だった。
x1,y1,x2,y2が全て0から200までの整数だったら、200x200の配列を塗りつぶすだけの問題になる。

そして、座標圧縮すればそうなる。

ソースコード

int n;
int x1[100],y1[100],x2[100],y2[100];
vector<double> X,Y;

bool V[201][201];

int main()
{
	int cs=0;
	while(scanf("%d",&n),n)
	{
		double X1[100],X2[100],Y1[100],Y2[100];
		X.clear(); Y.clear();
		rep(i,n)
		{
			scanf("%lf%lf%lf%lf",X1+i,Y1+i,X2+i,Y2+i);
			X.pb(X1[i]); X.pb(X2[i]);
			Y.pb(Y1[i]); Y.pb(Y2[i]);
		}
		sort(all(X)); sort(all(Y));
		X.erase(unique(all(X)),X.end()); Y.erase(unique(all(Y)),Y.end());
		rep(i,n)
		{
			x1[i]=lower_bound(all(X),X1[i])-X.begin();
			x2[i]=lower_bound(all(X),X2[i])-X.begin();
			y1[i]=lower_bound(all(Y),Y1[i])-Y.begin();
			y2[i]=lower_bound(all(Y),Y2[i])-Y.begin();
		}
		
		rep(i,201)fill_n(V[i],201,0);
		rep(i,n)for(int x=x1[i];x<x2[i];x++)
		for(int y=y1[i];y<y2[i];y++)V[y][x]=1;
		
		double ans=0;
		rep(i,201)rep(j,201)if(V[i][j])ans+=(X[j+1]-X[j])*(Y[i+1]-Y[i]);
		
		printf("Test case #%d\n",++cs);
		printf("Total explored area: %.2f\n\n",ans);
	}
	return 0;
}