这题二话不说, 用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;
}