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;
}