USACO 3.1 Shaping Regions 形成的区域

　　这题二话不说, 用map[i][j]表示坐标为i, j的点是什么颜色的.. 很快就写出来了, 但是内存超过了,, 内存最多16MB.
　　没办法, 只好另辟思路, 但是在数据压缩方面我又很弱, 就看标程也花了两三天的时间, 今天终于是看懂了..
　　用rect记录所有矩形的坐标以及相应的颜色.
　　程序具体的步骤如下:

　　输入A, B, N. 记录第一个矩形: (0, 0) (A, B), 颜色为1
　　接着读入其余的矩形, 设当前是第i个
　　对i之前所有的矩形迭代, 此时迭代到的是第j个.
　　判断i是否完全包含j, 即: i.x1 >= j.x1 && i.x2 >= j.x2 && i.y1 <= j.y1 && i.y2 >= j.y2..
　　　　若全包围的话, 将第j个矩形删除.
　　如果没包围的话, 就判断i会将j拆分成几个矩形, 并将j删除, 再分别拆分的矩形分别放入rect中.

/*
LANG: C
ID: zqy11001
PROG: rect1
*/
#include <stdio.h>
#include <string.h>
#define MAX 10001
#define getint(i) scanf("%d", &i)
#define loop(i, j, k, l)\
if(a.i l b.i){\
	t = a;\
	t.j = b.k;\
	tmp[n++] = t;\
	a.i = b.i;\
}

struct rect{
	int t;
	int x1, x2, y1, y2;
}rect[MAX];
int rr;
int color[2500];

int func(struct rect a, const struct rect b, struct rect *tmp)
{
	int n;
	struct rect t;
	if(b.x1 >= a.x2 || b.x2 <= a.x1 || b.y1 >= a.y2 || b.y2 <= a.y1){
		return 0;
	}
	if(b.x1 <= a.x1 && b.x2 >= a.x2 && b.y1 <= a.y1 && b.y2 >= a.y2){
		return -1;
	}

	n = 0;
	loop(x1, x2, x1, <=);
	loop(x2, x1, x2, >=);
	loop(y1, y2, y1, <=);
	loop(y2, y1, y2, >=);
	return n;
}

int main(void)
{
	int n, nr, m;
	int a, b, i, j, k;
	struct rect t[4], cur;
	freopen("rect1.in", "r", stdin);
	freopen("rect1.out", "w", stdout);
	getint(a);
	getint(b);
	getint(n);

	rect[0].x1 = rect[0].y1 = 0;
	rect[0].x2 = a;
	rect[0].y2 = b;
	rect[0].t = 1;

	rr = 1;
	for(i = 1; i <= n; i++){
		scanf("%d%d%d%d%d", &rect[rr].x1, &rect[rr].y1, 
				&rect[rr].x2, &rect[rr].y2, &rect[rr].t);
		cur = rect[rr++];
		nr = rr - 1;
		for(j = 0; j < nr; j++){
			m = func(rect[j], cur, t);
			if(!m){
				continue;
			}
			if(m < 0){
				memmove(rect + j, rect + j + 1,
					sizeof(struct rect) * (rr - j - 1));
				j--;
				rr--;
				nr--;
				continue;
			}
			rect[j] = t[--m];
			while(m--){
				rect[rr++] = t[m];
			}
		}
	}
	memset(color, 0, sizeof(color));
	for(i = 0; i < rr; i++){
		color[rect[i].t - 1] += (rect[i].x2 - rect[i].x1) *
				(rect[i].y2 - rect[i].y1);
	}

	for(i = 0; i < 2500; i++){
		if(color[i]){
			printf("%d %d\n", i + 1, color[i]);
		}
	}
	return 0;
}