扫描线求周长： 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
2 #include
3 #include
4 #include
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>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]=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
2 #include
3 #include
4 #include
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>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 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]>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 //}