好久没做USACO了,都是因为这题,矩形切割之前完全不会,但看了04年薛矛的论文《解决动态统计问题的两把利刃——剖析线段树与矩形切割》 顺利1A,关于矩形切割部分,他的论文讲的很仔细,推荐去看看。网上到处可以搜索到,这里就不再提供链接了
下面部分引用自薛矛的论文
矩形集合中已有矩形(x1,y1,x2,y2),现加入矩形(x3,y3,x4,y4)。它们的位置关系可以有很多种(有17种之多),这里就不一一列举了。但无论它们的位置关系如何复杂,运用线段切割的思想来进行矩形切割,就会变得十分明了。我们将矩形的切割正交分解,先进行x方向上的切割,再进行y方向的切割。如下图所示:
插入矩形(x3,y3,x4,y4)后,对矩形(x1,y1,x2,y2)进行切割。
- Step 1:首先从x方向上切。把线段(x1,x2)切成(x1,x3),(x4,x2)两条线段。于是相应地,我们就把两个矩形切了出来——(x1,y1,x3,y2),(x4,y1,x2,y2)。把它们加到矩形集合中。去掉了这两个矩形后,我们要切的矩形就变为(x3,y1,x4,y2)。
- Step 2:接着我们再进行y方向上的切割。把线段(y1,y2)切成(y1,y3)。相应地又得到一个矩形(x3,y1,x4,y2)。把它放入矩形集合。
Step 3:剩下的矩形为(x3,y3,x4,y2),这个矩形已经被矩形(x3,y3,x4,y4)覆盖了,因此直接把它删掉。
我们可以归纳出矩形切割的思想:1、先对被切割矩形进行x方向上的切割。取(x1,x2),(x3,x4)的交集(k1,k2)
- ①若x1<k1,则加入矩形(x1,y1,k1,y2)
- ②若k2<x2,则加入矩形(k2,y1,x2,y2)
- 2、再对切剩的矩形(k1,y1,k2,y2) 进行y 方向上的切割。取(y1,y2),(y3,y4)的交集(k3,k4)
- ①若y1<k3,则加入矩形(k1,y1,k2,k3)
- ②若k4<y2,则加入矩形(k1,k4,k2,y2)
- 3、把矩形(x1,y1,x2,y2)从矩形集合中删除。
切割过程的代码如下(PASCAL描述):1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19Procedure Cut(x1,y1,x2,y2,Direction)
Var k1,k2
Begin
Case Direction of
1:Begin
k1 := Max(x1,x3) {计算线段(x1,x2),(x3,x4)交集的左边界}
k2 := Min(x2,x4) {计算线段(x1,x2),(x3,x4)交集的右边界}
if x1 < k1 then Add(x1,y1,k1,y2)
if k2 < x2 then Add(k2,y1,x2,y2)
Cut(k1,y1,k2,y2,Direction+1)
End
2:Begin
k1 := Max(y1,y3)
k2 := Min(y2,y4)
if y1 < k1 then Add(x1,y1,x2,k1)
if k2 < y2 then Add(x1,k2,x2,y2)
End
End
End
其中Add是加入矩形的过程。
我的代码1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65/*
ID:shiryuw1
PROG:rect1
LANG:C++
*/
using namespace std;
int ans[2505]={0};
struct prog{
int llx,lly,urx,ury,color;
}rect[1005];
int area;
void DFS(int lx,int ly,int rx,int ry,int t)
{
if(t==0)
return ;
if(rect[t].llx>=rx||rect[t].lly>=ry||rect[t].urx<=lx||rect[t].ury<=ly)
{
DFS(lx,ly,rx,ry,t-1);
}
else
{
int k1,k2,k3,k4;
k1=max(lx,rect[t].llx);
k2=min(rx,rect[t].urx);
if(lx<k1)
DFS(lx,ly,k1,ry,t-1);
if(rx>k2)
DFS(k2,ly,rx,ry,t-1);
k3=max(ly,rect[t].lly);
k4=min(ry,rect[t].ury);
if(ly<k3)
DFS(k1,ly,k2,k3,t-1);
if(ry>k4)
DFS(k1,k4,k2,ry,t-1);
//cout<<k1<<' '<<k2<<' '<<k3<<' '<<k4<<endl;
ans[rect[t].color]+=abs(k2-k1)*abs(k4-k3);
area-=abs(k2-k1)*abs(k4-k3);
}
}
int main()
{
freopen("rect1.in","r",stdin);
freopen("rect1.out","w",stdout);
int a,b,n;
scanf("%d%d%d",&a,&b,&n);
int i,j;
memset(ans,0,sizeof(ans));
for(i=1;i<=n;i++)
scanf("%d%d%d%d%d",&rect[i].llx,&rect[i].lly,&rect[i].urx,&rect[i].ury,&rect[i].color);
area=a*b;
DFS(0,0,a,b,n);
ans[1]+=area;
for(i=1;i<2505;i++)
if(ans[i])
printf("%d %d\n",i,ans[i]);
return 0;
}