Shaping Regions USACO 3.1

这题不会,直接的看的题解,方法很多,不过感觉都没见过啊,选了第一个漂浮法看了好久才搞懂

漂浮法

以逆序来进行放置，即n to 1。逆序的好处在于放置一个矩形后，俯视看到的就是最终俯视该矩形应该看到的。因为挡着它的矩形在之前已经放置好了，所以可直接统计，为递归创造了条件。每放一个矩形，可以想象成将其扔入一密度很大的海水底部，海分成了n层,然后矩形开始向上浮。在上浮过程中若碰撞到其他的矩形则断裂成几个小矩形，继续上浮，直到浮出水面。于是想到用个递归来模拟上浮过程。

解释下,就是倒过来放,先放最上面一个,因为水面无拦截的矩形,直接飘到水面,被看到全部-----对应最后画的矩形肯定没有被覆盖

然后是倒数第二个,放到水底,快要到水面时,如果和上面的有交界.假设与上面的矩形重叠的部分会被留下（相当于被盖住了）,额外的部分被切割后继续上浮,被看到.随后重复...注意上浮过程是个迭代过程,会和上面的每一层产生一次切割过程(有相交就切割).

关键是切割后,继续上浮的面积怎么求。看NOCOW第一个解法,看了好久才搞懂.先上个图

黑色方块代表上面的遮挡矩形,下方的矩形产生的切割后上浮部分,可以完全划分到这1-4个区域中（区域组合有多种，这是一种）。

1区域产生上浮部分的条件是ly<y1[h],即下面矩形的ly<黑色的ly。

可能有人要问若ry<黑色的ly不是完全没有切割?即使这样也满足在1区域的条件。

2 3 4同理...

然后是可以看到这4个区域黑线一个边界外,每个区域还有一条红线作为边界,

同样要满足这个约束条件,对1来说,右边的红线表示1里的上浮矩形的x坐标不能超过黑色矩形的rx

1区域的上浮矩形的lx=min(OriginalLx,BlackRx),rx=min(OriginalRx,BlackRx),不管怎样就是不能越过BlackRx,同时 ry<BlackLy...

可能又有人要问若OriginalLx，OriginalRx,都大于BlackRx此时上浮不是1跳条线,没有了？

此时说明上浮矩形跑到了2区域,同理2区域会做相同处理,不用担心...

真是难,照着别人代码敲的,大牛们的脑子里长的啥,搞不懂啊搞不懂

 1 /*
 2 
 3 ID: hubiao cave
 4 
 5 PROG: rect1
 6 
 7 LANG: C++
 8 
 9 */
10 
11 
12 
13 
14 #include<iostream>
15 
16 #include<fstream>
17 
18 #include<string>
19 
20 using namespace std;
21 
22 
23 int x1[1002],y11[1002],x2[1002],y2[1002],color[1002]={1},cnt[2502],N;
24 
25 void cover(int lx,int ly,int rx,int ry,int c,int h);
26 int main()
27 
28 {
29 
30 
31     ifstream fin("rect1.in");
32 
33     ofstream fout("rect1.out");
34     
35     fin>>x2[0]>>y2[0]>>N;//最下面的那块
36     for(int i=1;i<=N;i++)
37         fin>>x1[i]>>y11[i]>>x2[i]>>y2[i]>>color[i];
38     cnt[color[N]]+=(y2[N]-y11[N])*(x2[N]-x1[N]);//最上面一层直接确定
39     for(int i=N-1;i>=0;i--)
40         cover(x1[i],y11[i],x2[i],y2[i],color[i],i+1);
41     
42     for(int i=1;i<=2500;++i)
43         if(cnt[i])
44         fout<<i<<" "<<cnt[i]<<endl;
45 
46     return 0;
47 
48 
49 }
50 void cover(int lx,int ly,int rx,int ry,int c,int h)
51 {
52     if(lx==rx||ly==ry)
53         return;
54     if(h>N)
55         cnt[c]+=(rx-lx)*(ry-ly);
56     else
57     {
58         if(ly<y11[h])
59             cover(min(lx,x2[h]),ly,min(rx,x2[h]),min(y11[h],ry),c,h+1);
60         if(rx>x2[h])
61             cover(max(x2[h],lx),min(y2[h],ly),rx,min(y2[h],ry),c,h+1);
62         if(ry>y2[h])
63             cover(max(lx,x1[h]),max(y2[h],ly),max(rx,x1[h]),ry,c,h+1);
64         if(lx<x1[h])
65             cover(lx,max(y11[h],ly),min(x1[h],rx),max(y11[h],ry),c,h+1);
66     }
67 
68 }