Smiling & Weeping

　　　　　　　　　　　　　　　　　　---- 人的情况和树相同。

　　　　　　　　　　　　　　　　它愈想开向高处和明亮处，它的根愈要向下，

　　　　　　　　　　　　　　　　　　向泥土，向黑暗处，向深处，向恶。

题目链接：Problem - 1255 (hdu.edu.cn)

求出覆盖多次的矩形面积(模板)

Talk is cheap , show me the code

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 #include<cstring>
 5 #include<algorithm>
 6 using namespace std;
 7 #define ls(p) p<<1
 8 #define rs(p) p<<1|1
 9 const int N = 10005;
10 int tag[N];             // 标志：线段是否有效，能否用于计算宽度
11 double length[N][2];       // 存放区间i的总宽度
12 double xx[N];           // 存放x坐标值，下标用lower_bound()查询
13 struct ScanLine{
14     double y;
15     double right_x , left_x;
16     int inout;          // 入边为1，出边为-1
17     ScanLine(){}
18     ScanLine(double y , double x2 , double x1 , int io):
19     y(y),right_x(x2),left_x(x1),inout(io){}
20 }line[N];
21 bool cmp(ScanLine &a , ScanLine &b){ return a.y < b.y; } // 对y坐标排序
22 void push_up(int p , int pl , int pr){
23     if(tag[p]) length[p][0] = xx[pr]-xx[pl];
24     else if(pl+1 == pr) length[p][0] = 0;
25     else length[p][0] = length[ls(p)][0]+length[rs(p)][0];
26 
27     if(tag[p] > 1) length[p][1] = length[p][0];     // 完全覆盖
28     else if(pl+1 == pr) length[p][1] = 0;
29     else if(tag[p] == 1) length[p][1] = length[ls(p)][0]+length[rs(p)][0];
30     else    length[p][1] = length[ls(p)][1]+length[rs(p)][1];
31 }
32 void update(int L ,int R , int io , int p ,int pl ,int pr){
33     if(L<=pl && pr<=R){
34         tag[p] += io;
35         push_up(p,pl,pr);
36         return ;
37     }
38     if(pl+1 == pr) return ;     // 叶子结点
39     int mid = pl+pr >> 1;
40     if(L <= mid) update(L,R,io,ls(p),pl,mid);
41     if(R >  mid) update(L,R,io,rs(p),mid,pr);
42     push_up(p,pl,pr);
43 }
44 int main()
45 {
46     int t=0,n;
47     scanf("%d",&t);
48     while(t--){
49         scanf("%d",&n);
50         int cnt=0;
51         while(n--){
52             double x1,x2,y1,y2;
53             // 输入矩形
54             scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
55             line[++cnt] = ScanLine(y1,x2,x1,1);
56             xx[cnt] = x1;
57             line[++cnt] = ScanLine(y2,x2,x1,-1);
58             xx[cnt] = x2;
59         }
60         sort(xx+1 ,xx+cnt+1);
61         sort(line+1 , line+cnt+1 , cmp);
62         int num = unique(xx+1,xx+1+cnt)-(xx+1);
63         memset(tag,0,sizeof(tag));
64         memset(length,0,sizeof(length));
65         double ans = 0;
66         // 扫描所有入边和出边
67         for(int i = 1; i <= cnt; i++){
68             int L,R;
69             ans += length[1][1]*(line[i].y-line[i-1].y);
70             L = lower_bound(xx+1 , xx+num+1 , line[i].left_x)-xx;
71             R = lower_bound(xx+1 , xx+num+1 , line[i].right_x)-xx;
72             update(L,R,line[i].inout,1,1,num);
73         }
74         printf("%.2f\n",ans);
75     }
76     return 0;
77 }

所谓无底深渊，下去，也是前程万丈

文章到此结束，我们下次再见