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

相关日志