USACO 3.1.4 Shaping Regions 形成的區域
本文正體字版由OpenCC轉換
姑且讓我把它歸爲計算幾何類，從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