USACO 3.1.4 Shaping Regions 形成的区域
姑且让我把它归为计算几何类，从NOCOW上得知这道题有多种解法，标准解法是离散化。但是处于简单易行考虑，最优解法是倒序染色+分割矩形。看了梦里醉逍遥大牛的题解，我深受启发，在此orz(话说我今天刚懂了orz的意思)。
思路大概是这样的，首先读入所有的矩形。我们可以发现最后覆盖的矩形不会被其他矩形覆盖，所以可以考虑从后向前覆盖。
对于每个矩形，我们把它和有可能覆盖在它上面的矩形(就是出现在当前矩形后面的矩形)比较，如果两个矩形有重叠部分就把重叠部分去掉，把当前矩形分成几个小矩形递归进行分割。直到当前矩形与后面的矩形全部没有公共部分，累加矩形的面积。
本题关键就在于分割矩形，一定要仔细分析，避免出错。我就在分割的时候将一个变量名写错了，导致检查2个小时。
分割矩形简单分为四种情况，上下左右四个方向有重叠，由于递归的分割，分割完的小矩形会有可能继续分割。
我还有个小小的疑惑：看了许多大牛用这种方法写的题解，貌似几乎所有人都把保存不同颜色的面积的数组开成2500个元素。这个数字很令我疑惑。我只是简单的#define MAX 1001，测试点就全过了。到底为什么呢？疑惑中。
代码
/*
ID: cmykrgb1
PROG: rect1
LANG: C
*/
#include <stdio.h>
#define MAX 1001
typedef struct
{
long px,py,qx,qy,color;
}rectangular;
FILE *fi,*fo;
long A,B,n,cur_c;
long sq[MAX];
rectangular R[MAX];
void compute(long px,long py,long qx,long qy,long posi)
{
do posi++;
while (posi<=n &&
( R[posi].px>=qx ||
R[posi].py>=qy ||
R[posi].qx<=px ||
R[posi].qy<=py ) );
if (posi>n) //未找到重叠部分
sq[cur_c]+=(qx-px)*(qy-py);
else //有重叠部分 拆分矩形
{
if (px<R[posi].px)
{
compute(px,py,R[posi].px,qy,posi);
px=R[posi].px;
}
if (qx>R[posi].qx)
{
compute(R[posi].qx,py,qx,qy,posi);
qx=R[posi].qx;
}
if (py<R[posi].py)
compute(px,py,qx,R[posi].py,posi);
if (qy>R[posi].qy)
compute(px,R[posi].qy,qx,qy,posi);
}
}
int main(void)
{
long i;
long px,py,qx,qy,color;
fi=fopen("rect1.in","r");
fo=fopen("rect1.out","w");
fscanf(fi,"%ld%ld%ld",&A,&B,&n);
for (i=1;i<=n;i++)
{
fscanf(fi,"%ld%ld%ld%ld%ld",
&px,&py,&qx,&qy,&color);
R[i].px=px;
R[i].py=py;
R[i].qx=qx;
R[i].qy=qy;
R[i].color=color;
}
R[0].qx=A;R[0].qy=B;R[0].color=1;
for (i=n;i>=0;i--)
{
cur_c=R[i].color;
compute(R[i].px,R[i].py,R[i].qx,R[i].qy,i);
}
for (i=1;i<MAX;i++)
if (sq[i])
fprintf(fo,"%ld %ldn",i,sq[i]);
fclose(fi);
fclose(fo);
return 0;
}
上次修改时间 2017-02-03