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

相關日誌