继续矩形切割。
直接上个程序改了改。这次是问颜色不同的矩形覆盖后剩下多少种颜色的矩形,并且求出来面积。
直接标记下颜色,然后相同颜色的面积加一起即可。
本来应该一次AC的。。。WA了数次。。。输出没看清楚 = = color与colors考虑到了。。。但是is 和are没注意 = =T T 。。。我还以为是精度问题。。全换成int了。。。double也过了。
#include <queue> #include <stack> #include <math.h> #include <stdio.h> #include <stdlib.h> #include <iostream> #include <limits.h> #include <string.h> #include <string> #include <algorithm> using namespace std; const int MAX = 105*2; int x[MAX]; int y[MAX]; struct rectangle{ int lx,ly,rx,ry;int col;}; rectangle r[105]; int map[MAX][MAX]; int area[105]; int find(int a[],int m,int x) { int beg = 0,end = m-1; while( beg <= end ) { int mid = (beg+end) >> 1; if( x == a[mid] ) return mid; if( x > a[mid] ) beg = mid + 1; else end = mid; } } void solve(int n,int cnt) { for(int i=0; i<n; i++) { int x1 = find(x,cnt,r[i].lx); int x2 = find(x,cnt,r[i].rx); int y1 = find(y,cnt,r[i].ly); int y2 = find(y,cnt,r[i].ry); for(int k=x1; k<x2; k++) for(int j=y1; j<y2; j++) map[k][j] = r[i].col; } for(int i=0; i<cnt-1; i++) for(int k=0; k<cnt-1; k++) if( map[i][k] ) area[map[i][k]] += (x[i+1] - x[i])*(y[k+1] - y[k]); } int main() { int n,cnt,ind = 1,h,w; bool flag = false; while( ~scanf("%d%d",&h,&w) && (h || w) ) { if( flag ) printf("\n"); flag = true; cnt = 0; memset(map,0,sizeof(map)); scanf("%d",&n); for(int i=0; i<n; i++) { scanf("%d%d%d%d%d",&r[i].lx,&r[i].ly,&r[i].rx,&r[i].ry,&r[i].col); x[cnt] = r[i].lx; y[cnt++] = r[i].ly; x[cnt] = r[i].rx; y[cnt++] = r[i].ry; } for(int i=0; i<MAX; i++) area[i] = 0; sort(x,x+cnt); sort(y,y+cnt); solve(n,cnt); int ans = 0; printf("Case %d:\n",ind++); for(int i=0; i<MAX; i++) if( area[i] ) { printf("%d %d\n",i,area[i]); ans++; } if( ans == 1 ) printf("There is %d color left on the wall.\n",ans); else printf("There are %d colors left on the wall.\n",ans); } return 0; }