扫描线求周长： hdu1828 Picture(线段树+扫描线+矩形周长)
参考链接：https://blog.csdn.net/konghhhhh/java/article/details/78236036
假想有一条扫描线，从左往右（从右往左），或者从下往上（从上往下）扫描过整个多边形（或者说畸形。。多个矩形叠加后的那个图形）。如果是竖直方向上扫描，则是离散化横坐标，如果是水平方向上扫描，则是离散化纵坐标。下面的分析都是离散化横坐标的，并且从下往上扫描的。
扫描之前还需要做一个工作，就是保存好所有矩形的上下边，并且按照它们所处的高度进行排序，另外如果是上边我们给他一个值-1，下边给他一个值1，我们用一个结构体来保存所有的上下边
struct segment
{
double l,r,h; //l，r表示这条上下边的左右坐标，h是这条边所处的高度
int f; //所赋的值，1或-1
}
接着扫描线从下往上扫描，每遇到一条上下边就停下来，将这条线段投影到总区间上（总区间就是整个多边形横跨的长度），这个投影对应的其实是个插入和删除线段操作。还记得给他们赋的值1或-1吗，下边是1，扫描到下边的话相当于往总区间插入一条线段，上边-1，扫描到上边相当于在总区间删除一条线段（如果说插入删除比较抽象，那么就直白说，扫描到下边，投影到总区间，对应的那一段的值都要增1，扫描到上边对应的那一段的值都要减1，如果总区间某一段的值为0，说明其实没有线段覆盖到它，为正数则有，那会不会为负数呢？是不可能的，可以自己思考一下）。
每扫描到一条上下边后并投影到总区间后，就判断总区间现在被覆盖的总长度，然后用下一条边的高度减去当前这条边的高度，乘上总区间被覆盖的长度，就能得到一块面积，并依此做下去，就能得到最后的面积
（这个过程其实一点都不难，只是看文字较难体会，建议纸上画图，一画即可明白，下面献上一图希望有帮助） 
例题：一、Atlantis HDU - 1542（覆盖面积）
题意：
给你一些矩形，让你求出来它们的总面积是多少（注意这些矩形可能会重叠）
题解：
就是上面讲的扫描线方法
1 #include<stdio.h>
2 #include<string.h>
3 #include<iostream>
4 #include<algorithm>
5 using namespace std;
6 #define lson i<<1,l,m
7 #define rson i<<1|1,m+1,r
8 const int maxn=205;
9 double w[maxn<<1];
10 struct trees
11 {
12 double l,r,h;
13 int d;
14 trees() {}
15 trees(double a,double b,double c,int d): l(a),r(b),h(c),d(d) {}
16 bool operator <(const trees q)const
17 {
18 return h<q.h;
19 }
20 } tree[maxn<<2];
21 int cnt[maxn<<2];
22 double sum[maxn<<2];
23 void pushdown(int rt,int l,int r)
24 {
25 int m=(l+r)>>1;
26 if(cnt[rt]!=-1)
27 {
28 cnt[rt<<1]=cnt[rt<<1|1]=cnt[rt];
29 sum[rt<<1]=(cnt[rt] ? (w[m+1]-w[l]) : 0);
30 sum[rt<<1|1]=(cnt[rt] ? (w[r+1]-w[m+1]) : 0);
31 }
32 }
33 void pushup(int rt,int l,int r)
34 {
35 if(cnt[rt<<1] || cnt[rt<<1|1])
36 {
37 cnt[rt]=-1;
38 }
39 else if(cnt[rt<<1]!=cnt[rt<<1|1])
40 {
41 cnt[rt]=-1;
42 }
43 else cnt[rt]=cnt[rt<<1];
44 sum[rt]=sum[rt<<1]+sum[rt<<1|1];
45 }
46 void build(int rt,int l,int r)
47 {
48 if(l==r)
49 {
50 sum[rt]=0.0;
51 cnt[rt]=0;
52 return;
53 }
54 int m=(l+r)>>1;
55 build(rt<<1,l,m); //就是这里rt<<1的位置写错了，卧槽。。
56 build(rt<<1|1,m+1,r);
57 pushup(rt,l,r);
58 }
59 void update(int L,int R,int C,int rt,int l,int r)
60 {
61 if(l>=L && r<=R)
62 {
63 if(cnt[rt]!=-1)
64 {
65 cnt[rt]+=C;
66 sum[rt]=(cnt[rt] ? (w[r+1]-w[l]) : 0);
67 return;
68 }
69 }
70 pushdown(rt,l,r);
71 int m=(l+r)>>1;
72 if(m>=L) update(L,R,C,rt<<1,l,m);
73 if(R>m) update(L,R,C,rt<<1|1,m+1,r);
74 pushup(rt,l,r);
75 }
76 int searchs(int l,int r,double x)
77 {
78 int m=-1;
79 while(l<=r)
80 {
81 m=(l+r)>>1;
82 if(w[m]>x) r=m-1;
83 else if(w[m]<x) l=m+1;
84 else break;
85 }
86 return m;
87 }
88 //void PushDown(int i,int l,int r)
89 //
90 //{
91 //
92 // int m=(l+r)/2;
93 //
94 // if(cnt[i]!=-1)
95 //
96 // {
97 //
98 // cnt[i*2]=cnt[i*2+1]=cnt[i];
99 //
100 // sum[i*2]= (cnt[i]?(w[m+1]-w[l]):0) ;
101 //
102 // sum[i*2+1]= (cnt[i]?(w[r+1]-w[m+1]):0) ;
103 //
104 // }
105 //
106 //}
107 //
108 //void PushUp(int i,int l,int r)
109 //
110 //{
111 //
112 // if(cnt[i*2]==-1 || cnt[i*2+1]==-1)
113 //
114 // cnt[i]=-1;
115 //
116 // else if(cnt[i*2] != cnt[i*2+1])
117 //
118 // cnt[i]=-1;
119 //
120 // else
121 //
122 // cnt[i]=cnt[i*2];
123 //
124 // sum[i]=sum[i*2]+sum[i*2+1];
125 //
126 //}
127
128 //void build(int i,int l,int r)
129 //
130 //{
131 //
132 // if(l==r)
133 //
134 // {
135 //
136 // cnt[i]=0;
137 //
138 // sum[i]=0.0;
139 //
140 // return ;
141 //
142 // }
143 //
144 // int m=(l+r)/2;
145 //
146 // build(lson);
147 //
148 // build(rson);
149 //
150 // PushUp(i,l,r);
151 //
152 //}
153 //
154 //void update(int ql,int qr,int v,int i,int l,int r)
155 //
156 //{
157 //
158 // if(ql<=l && r<=qr)
159 //
160 // {
161 //
162 // if(cnt[i]!=-1)
163 //
164 // {
165 //
166 // cnt[i]+=v;
167 //
168 // sum[i] = (cnt[i]? (w[r+1]-w[l]):0);
169 //
170 // return ;
171 //
172 // }
173 //
174 // }
175 //
176 // pushdown(i,l,r);
177 //
178 // int m=(l+r)/2;
179 //
180 // if(ql<=m) update(ql,qr,v,lson);
181 //
182 // if(m<qr) update(ql,qr,v,rson);
183 //
184 // pushup(i,l,r);
185 //
186 //}
187 //
188 //int searchs(double key,int n,double d[])
189 //
190 //{
191 //
192 // int l=1,r=n;
193 //
194 // while(r>=l)
195 //
196 // {
197 //
198 // int m=(r+l)/2;
199 //
200 // if(d[m]==key)
201 //
202 // return m;
203 //
204 // else if(d[m]>key)
205 //
206 // r=m-1;
207 //
208 // else
209 //
210 // l=m+1;
211 //
212 // }
213 //
214 // return -1;
215 //
216 //}
217 int main()
218 {
219 int n,k=0;
220 while(~scanf("%d",&n) && n)
221 {
222 int ans1=0,ans2=0;
223 for(int i=1;i<=n;++i)
224 {
225 double x1,y1,x2,y2;
226 scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
227 w[++ans1]=x1;
228 w[++ans1]=x2;
229 tree[++ans2]=trees(x1,x2,y1,1);
230 tree[++ans2]=trees(x1,x2,y2,-1);
231 }
232 sort(w+1,w+1+ans1);
233 sort(tree+1,tree+1+ans2);
234 int ans=1;
235 for(int i=2;i<=ans1;++i)
236 {
237 if(w[i]!=w[i-1])
238 {
239 w[++ans]=w[i];
240 }
241 }
242 build(1,1,ans-1);
243 double ret=0.0;
244 for(int i=1;i<ans2;++i)
245 {
246 int l=searchs(1,ans,tree[i].l);
247 int r=searchs(1,ans,tree[i].r)-1;
248 //printf("%d %d %lf %lf\n",l,r,tree[i].l,tree[i].r);
249 if(l<=r) update(l,r,tree[i].d,1,1,ans-1);
250 ret+=sum[1]*(tree[i+1].h-tree[i].h);
251 //printf("%lf %lf %lf\n",sum[1],tree[i+1].h,tree[i].h);
252 }
253 printf("Test case #%d\nTotal explored area: %.2lf\n\n",++k,ret);
254 }
255 return 0;
256 }
例题： 二、覆盖的面积 HDU - 1255（重叠两次的面积）
题意：
给你一些矩形，让你求被覆盖至少两次区域的面积
题解：
和之前那个差不多，具体见代码
代码：
1 #include<stdio.h>
2 #include<string.h>
3 #include<iostream>
4 #include<algorithm>
5 using namespace std;
6 #define lch(i) ((i)<<1)
7 #define rch(i) ((i)<<1|1)
8 const int maxn=2005;
9 double w[maxn];
10 struct shudui
11 {
12 double l,r,h;
13 int d;
14 shudui(){}
15 shudui(double a,double b,double c,int d): l(a),r(b),h(c),d(d){}
16 bool operator < (const shudui q)const
17 {
18 return h<q.h;
19 }
20 }v[maxn];
21 struct trees
22 {
23 int l,r,m,cnt;
24 double s,ss;
25 }tree[maxn<<2];
26 int n;
27 void build(int l,int r,int rt)
28 {
29 tree[rt].l=l;
30 tree[rt].r=r;
31 int m=(l+r)>>1;
32 tree[rt].m=m;
33 tree[rt].s=tree[rt].ss=tree[rt].cnt=0;
34 if(l==r)
35 {
36 return;
37 }
38 build(l,m,rt<<1);
39 build(m+1,r,rt<<1|1);
40 }
41 void pushup(int rt) //这种方法cnt是不会为负值的
42 {
43 if(tree[rt].cnt)
44 {
45 tree[rt].s=w[tree[rt].r+1]-w[tree[rt].l];
46 }
47 else if(tree[rt].l==tree[rt].r)
48 tree[rt].s=0;
49 else
50 tree[rt].s=tree[rt<<1].s+tree[rt<<1|1].s;
51 if(tree[rt].cnt>1)
52 tree[rt].ss=w[tree[rt].r+1]-w[tree[rt].l];
53 else if(tree[rt].l==tree[rt].r)
54 tree[rt].ss=0;
55 else if(tree[rt].cnt==1)
56 {
57 tree[rt].ss=tree[rt<<1].s+tree[rt<<1|1].s;
58 }
59 else tree[rt].ss=tree[rt<<1].ss+tree[rt<<1|1].ss;
60 }
61 void update(int L,int R,int C,int rt)
62 {
63 if(tree[rt].l==L && tree[rt].r==R)
64 {
65 tree[rt].cnt+=C; //这种方法cnt不往下传也不往上传
66 pushup(rt);
67 return;
68 }
69 int m=tree[rt].m;
70 if(R<=m) update(L,R,C,rt<<1);
71 else if(m<L) update(L,R,C,rt<<1|1);
72 else
73 {
74 update(L,m,C,rt<<1);
75 update(m+1,R,C,rt<<1|1);
76 }
77 pushup(rt);
78 }
79 //void cal(int rt)
80 //{
81 // if(tree[rt].cnt)
82 // tree[rt].s = w[tree[rt].r+1] - w[tree[rt].l];
83 // else if(tree[rt].l == tree[rt].r)
84 // tree[rt].s=0;
85 // else
86 // tree[rt].s = tree[lch(rt)].s + tree[rch(rt)].s;
87 ///**************************************************/
88 // if(tree[rt].cnt > 1)
89 // tree[rt].ss = w[tree[rt].r+1] - w[tree[rt].l];
90 // else if(tree[rt].l == tree[rt].r)
91 // tree[rt].ss = 0;
92 // else if(tree[rt].cnt == 1)
93 // tree[rt].ss = tree[lch(rt)].s + tree[rch(rt)].s;
94 // else
95 // tree[rt].ss = tree[lch(rt)].ss + tree[rch(rt)].ss;
96 //}
97 //
98 //void update(int l , int r ,int v ,int rt)
99 //{
100 // if(tree[rt].l==l && tree[rt].r==r)
101 // {
102 // tree[rt].cnt += v;
103 // cal(rt);
104 // return ;
105 // }
106 // int mid=tree[rt].m;
107 // if(r<=mid) update(l,r,v,lch(rt));
108 // else if(l>mid) update(l,r,v,rch(rt));
109 // else
110 // {
111 // update(l,mid,v,lch(rt));
112 // update(mid+1,r,v,rch(rt));
113 // }
114 // cal(rt);
115 //}
116 int searchs(int l,int r,double x)
117 {
118 int m;
119 while(l<=r)
120 {
121 m=(l+r)>>1;
122 if(w[m]>x) r=m-1;
123 else if(w[m]<x) l=m+1;
124 else break;
125 }
126 return m;
127 }
128 //int searchs(int low ,int high,double key)
129 //{
130 // while(low <= high)
131 // {
132 // int mid=(low+high)>>1;
133 // if(w[mid] == key)
134 // return mid;
135 // else if(w[mid] < key)
136 // low=mid+1;
137 // else
138 // high=mid-1;
139 // }
140 // return -1;
141 //}
142 int main()
143 {
144 int t;
145 scanf("%d",&t);
146 while(t--)
147 {
148 scanf("%d",&n);
149 int ans1=0,ans2=0;
150 for(int i=1;i<=n;++i)
151 {
152 double x1,y1,x2,y2;
153 scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
154 w[++ans1]=x1;
155 w[++ans1]=x2;
156 v[++ans2]=shudui(x1,x2,y1,1);
157 v[++ans2]=shudui(x1,x2,y2,-1);
158 }
159 sort(w+1,w+1+ans1);
160 sort(v+1,v+1+ans2);
161 int k=1;
162 for(int i=2;i<=ans1;++i)
163 {
164 if(w[i]!=w[i-1])
165 w[++k]=w[i];
166 }
167 build(1,k-1,1);
168 double ret=0;
169 for(int i=1;i<ans2;++i)
170 {
171 int l=searchs(1,k,v[i].l);
172 int r=searchs(1,k,v[i].r)-1; //不知道什么时候出现一个k-1
173 if(l<=r)
174 //printf("%d %d %lf %lf\n",l,r,v[i].l,v[i].r);
175 update(l,r,v[i].d,1);
176 ret+=tree[1].ss*(v[i+1].h-v[i].h);
177 }
178 printf("%.2lf\n",ret);
179 }
180 return 0;
181 }
182 //int main()
183 //{
184 // int T;
185 // scanf("%d",&T);
186 // while(T--)
187 // {
188 // scanf("%d",&n);
189 // int i,k;
190 // for(i=0,k=0; i<n; i++,k+=2)
191 // {
192 // double x1,y1,x2,y2;
193 // scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
194 // w[k]=x1; w[k+1]=x2;
195 // v[k].l=x1; v[k].r=x2; v[k].h=y1; v[k].d=1;
196 // v[k+1].l=x1; v[k+1].r=x2; v[k+1].h=y2; v[k+1].d=-1;
197 // }
198 // sort(w,w+k);
199 // sort(v,v+k);
200 // int m=1;
201 // for(i=1; i<k; i++)
202 // if(w[i]!=w[i-1])
203 // w[m++]=w[i];
204 //
205 // build(0,m-1,1);
206 // double res=0;
207 // for(i=0; i<k-1; i++)
208 // {
209 // int l=searchs(0,m-1,v[i].l);
210 // int r=searchs(0,m-1,v[i].r)-1;
211 // //printf("%d %d\n",l,r);
212 // update(l,r,v[i].d,1);
213 // res += tree[1].ss*(v[i+1].h - v[i].h);
214 // }
215 // printf("%.2lf\n",res);
216 // }
217 // return 0;
218 //}