覆盖的面积（扫描线求面积交

 1 #include <bits/stdc++.h>
 2 #define pb push_back
 3 #define db double
 4 using namespace std;
 5 const int N = 100010;
 6 int n;
 7 struct Segment
 8 {
 9     double x, y1, y2;
10     int k;
11     bool operator< (const Segment &t)const
12     {
13         return x < t.x;
14     }
15 }seg[N * 2];
16 struct Node
17 {
18     int l, r;
19     int cnt;
20     double len;
21     double len2;
22 }tr[N * 8];
23 
24 vector<double> ys;
25 int find(db y){
26     return lower_bound(ys.begin(),ys.end(),y)-ys.begin();
27 }
28 inline void push_up(int u)
29 {
30     if (tr[u].cnt) tr[u].len = ys[tr[u].r + 1] - ys[tr[u].l];//当前区间有覆盖，加上当前区间代表线段的长度
31     else if (tr[u].l != tr[u].r)
32     {
33         tr[u].len = tr[u << 1].len + tr[u << 1 | 1].len;//将当前的总长度传递到根节点
34     }
35     else tr[u].len = 0;
36 
37     if(tr[u].cnt>1) tr[u].len2=ys[tr[u].r + 1] - ys[tr[u].l];//区间多次覆盖
38     else if(tr[u].l==tr[u].r) tr[u].len2=0;
39     else if(tr[u].cnt==1) tr[u].len2=tr[u<<1].len+tr[u<<1|1].len;
40     else tr[u].len2=tr[u<<1].len2+tr[u<<1|1].len2;
41 }
42 inline void build(int u, int l, int r)
43 {
44     tr[u] = {l, r, 0, 0,0};
45     if (l != r)
46     {
47         int mid = l + r >> 1;
48         build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
49     }
50 }
51 void change(int u,int l,int r,int k){
52     if(tr[u].l >= l && tr[u].r <= r){
53         tr[u].cnt += k;
54         push_up(u);
55     }
56     else {
57         int mid = tr[u].l + tr[u].r >> 1;
58         if( l <= mid ) change(u<<1,l,r,k);
59         if(r>mid) change(u<<1|1,l,r,k);
60         push_up(u);
61     }
62 }
63 int main(){
64     int t;
65     scanf("%d",&t);
66     while(t--){
67         scanf("%d",&n);
68         ys.clear();
69         for(int i=0,j=0;i<n;i++){
70             double x1,y1,x2,y2;
71             scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
72             ys.pb(y1);
73             ys.pb(y2);
74             seg[j++]={x1,y1,y2,1};
75             seg[j++]={x2,y1,y2,-1};
76         }
77         sort(ys.begin(),ys.end());
78         ys.erase(unique(ys.begin(),ys.end()),ys.end());
79         sort(seg,seg+2*n);
80         build(1,0,ys.size()-2);//线段个数比点的个数少1
81 
82         db res=0;
83         for(int i=0;i<n*2;i++){
84             if(i > 0) res += tr[1].len2*(seg[i].x-seg[i-1].x);
85             change(1,find(seg[i].y1),find(seg[i].y2)-1,seg[i].k);
86         }
87         printf("%.2lf\n", res);
88     }
89 }