paint the wall(矩形离散化).cpp

杭电acm解题报告2001---2099.

#include <cstdio>
#include <string>
#include <algorithm>
using namespace std;

int n,h,w,ls;
struct REC {
	int x1,y1,x2,y2;
	int c;
}paint[110];
int wall[210][210];
int col[110];
int X[210],Y[210];

int Bsearch(int * axis, int val)
{
	int pos = lower_bound(axis,axis+ls,val) - axis;
	return pos;
}

int main()
{
	int i,j,k;
	int t = 1;
	while(scanf("%d %d",&h,&w)==2) {
		if(h==0 && w==0) {
			break;
		}
		ls = 0;
		scanf("%d",&n);
		for(i=0;i<n;i++) {
			scanf("%d %d %d %d %d",&paint[i].x1,&paint[i].y1,&paint[i].x2,&paint[i].y2,&paint[i].c);
			X[ls] = paint[i].x1;
			X[ls+1] = paint[i].x2;
			Y[ls] = paint[i].y1;
			Y[ls+1] = paint[i].y2;
			//X[ls].index = X[ls+1].index = Y[ls].index = Y[ls+1].index = i;
			ls += 2;
		}
		sort(X,X+ls);
		sort(Y,Y+ls);

		memset(col,0,sizeof(col));
		memset(wall,0,sizeof(wall));
		for(i=0;i<n;i++) {
			int xp1 = Bsearch(X,paint[i].x1);
			int xp2 = Bsearch(X,paint[i].x2);
			int yp1 = Bsearch(Y,paint[i].y1);
			int yp2 = Bsearch(Y,paint[i].y2);
			for(j=xp1;j<xp2;j++) {
				for(k=yp1;k<yp2;k++) {
					wall[j][k] = paint[i].c;
				}
			}
		}

		for(i=0;i<ls;i++) {
			for(j=0;j<ls;j++) {
				col[ wall[i][j] ] += (X[i+1]-X[i])*(Y[j+1]-Y[j]);
			}
		}
		if(t > 1) {
			printf("\n");
		}
		printf("Case %d:\n", t ++);
		for(i=1,j=0;i<=100;i++) {
			if(col[i] != 0) {
				j ++;
				printf("%d %d\n", i,col[i]);
			}
		}
		printf(j==1? "There is 1 color left on the wall.\n" : "There are %d colors left on the wall.\n",j);
	}
}