扫描线求面积的并,交

扫描线求面积的并：题目

模板：

 1 #include <iostream>
 2 #include <algorithm>
 3 using namespace std;
 4 typedef long long ll;
 5 const int maxn = 210;
 6 int n;
 7 double x[maxn<<2];
 8 struct node{
 9     double l,r,h;
10     int flag;
11 }nd[maxn<<2];
12 
13 bool cmp(node u, node v)
14 {
15     return u.h<v.h;
16 }
17 
18 struct tree{
19     int l,r,cnt;
20     double len;
21 }tree[maxn<<2];
22 
23 void build(int rt,int left,int right){
24     tree[rt].l=left;
25     tree[rt].r=right;
26     tree[rt].len=0;
27     tree[rt].cnt=0;
28     if( left==right ) return ;
29     int mid=(left+right)>>1;
30     build(rt<<1,left,mid);
31     build(rt<<1|1,mid+1,right);
32 }
33 
34 int findPos(int l,int r,double val){
35     int mid;
36     while( l<=r ){
37         mid=(l+r)>>1;
38         if( x[mid]>val ) r=mid-1;
39         else if( x[mid]<val ) l=mid+1;
40         else break;
41     }
42     return mid;
43 }
44 
45 void pushUp(int rt){
46     if( tree[rt].cnt ){//非0,整段覆盖
47         tree[rt].len=x[tree[rt].r+1]-x[tree[rt].l];
48     }
49     else if( tree[rt].l==tree[rt].r )//叶子
50         tree[rt].len=0;
51     else tree[rt].len=tree[rt<<1].len+tree[rt<<1|1].len;
52 }
53 
54 void update(int rt,int left,int right,int val){
55     if( left<=tree[rt].l && tree[rt].r<=right ){
56         tree[rt].cnt+=val;
57         pushUp(rt);
58         return ;
59     }
60     int mid=(tree[rt].l+tree[rt].r)>>1;
61     if( left<=mid ) update(rt<<1,left,right,val);
62     if( right>mid ) update(rt<<1|1,left,right,val);
63     pushUp(rt);
64 }
65 
66 int main()
67 {
68     int cas=0;
69     int l,r;
70     double x1,x2,y1,y2;
71     while( ~scanf("%d",&n)&&n){
72         int cnt=0;
73         for(int i=1;i<=n;i++){
74             scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
75             x[++cnt]=x1;
76             nd[cnt].l=x1;
77             nd[cnt].r=x2;
78             nd[cnt].h=y1;
79             nd[cnt].flag=1;//下边
80             x[++cnt]=x2;
81             nd[cnt].l=x1;
82             nd[cnt].r=x2;
83             nd[cnt].h=y2;
84             nd[cnt].flag=-1;//上边
85         }
86         sort(x+1,x+1+cnt);
87         sort(nd+1,nd+1+cnt,cmp);
88         build(1,1,cnt);
89         double ans=0;
90         for(int i=1;i<=cnt;i++){
91             l=findPos(1,cnt,nd[i].l);
92             r=findPos(1,cnt,nd[i].r)-1;
93             update(1,l,r,nd[i].flag);
94             ans += tree[1].len*(nd[i+1].h-nd[i].h);
95         }
96         printf("Test case #%d
Total explored area: %.2f

",++cas,ans);
97     }
98     return 0;
99 }

扫描线先求面积的交：题目

模板：

  1 #include<iostream>
  2 #include<cstring>
  3 #include<cstdio>
  4 #include<algorithm>
  5 using namespace std;
  6 typedef long long ll;
  7 
  8 const int maxn=2010;
  9 int n, cnt;
 10 double x[maxn<<2];
 11 struct Node{
 12     double l,r,y;
 13     int flag;
 14 }node[maxn<<2];
 15 
 16 int cmp(Node a ,Node b){
 17     return a.y<b.y;
 18 }
 19 
 20 struct Tree{
 21     int l, r;
 22     double add,len1,len2;
 23 }tree[maxn<<2];
 24 
 25 int findPos(double val)//找val在x[]中出现的位置
 26 {
 27     int l=1, r=cnt;
 28     int mid;
 29     while(l<=r)
 30     {
 31         mid=(l+r)>>1;
 32         if(x[mid]<val) l=mid+1;
 33         else if(x[mid]>val) r=mid-1;
 34         else break;
 35     }
 36     return mid;
 37 }
 38 
 39 void build(int rt, int left, int right)
 40 {
 41     tree[rt].l=left;
 42     tree[rt].r=right;
 43     tree[rt].add=tree[rt].len1=tree[rt].len2=0;//全置0
 44     if(left==right)//叶子
 45     {
 46         return ;
 47     }
 48     int mid=(left+right)>>1;
 49     build(rt<<1,left,mid);
 50     build(rt<<1|1,mid+1,right);
 51 }
 52 void pushUp(int rt)
 53 {
 54     if(tree[rt].add>=2) tree[rt].len1=tree[rt].len2=x[tree[rt].r+1]-x[tree[rt].l];
 55     else if(tree[rt].add==1){
 56         tree[rt].len1=x[tree[rt].r+1]-x[tree[rt].l];
 57         if(tree[rt].l==tree[rt].r) tree[rt].len2=0;
 58         else tree[rt].len2=tree[rt<<1].len1+tree[rt<<1|1].len1;
 59     }
 60     else{
 61         if(tree[rt].l==tree[rt].r) tree[rt].len1=tree[rt].len2=0;
 62         else{
 63             tree[rt].len1=tree[rt<<1].len1+tree[rt<<1|1].len1;
 64             tree[rt].len2=tree[rt<<1].len2+tree[rt<<1|1].len2;
 65         }
 66     }
 67 }
 68 
 69 void update(int rt,int left,int right,int val){
 70     if(left<=tree[rt].l && tree[rt].r<=right){
 71         tree[rt].add+=val;
 72         pushUp(rt);
 73         return ;
 74     }
 75     int mid=(tree[rt].l+tree[rt].r)>>1;
 76     if( left<=mid ) update(rt<<1,left,right,val);
 77     if( right>mid ) update(rt<<1|1,left,right,val);
 78     pushUp(rt);
 79 }
 80 
 81 int main()
 82 {
 83     double x1,x2,y1,y2;
 84     int l,r,t;
 85     scanf("%d",&t);
 86     while(t--){
 87         cnt=0;
 88         memset(node, 0, sizeof(node));
 89         memset(tree, 0, sizeof(tree));
 90         scanf("%d",&n);
 91         for(int i=1;i<=n;i++){
 92             scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
 93             x[++cnt]=x1;
 94             node[cnt].l=x1;
 95             node[cnt].r=x2;
 96             node[cnt].y=y1;
 97             node[cnt].flag=1;//左边
 98             x[++cnt]=x2;
 99             node[cnt].l=x1;
100             node[cnt].r=x2;
101             node[cnt].y=y2;
102             node[cnt].flag=-1;//右边
103         }
104         sort(x+1,x+cnt+1);
105         sort(node+1,node+cnt+1,cmp);
106         build(1,1,cnt);
107         double ans=0;
108 
109         l=findPos(node[1].l);
110         r=findPos(node[1].r)-1;
111         update(1,l,r,node[1].flag);
112         for(int i=2;i<=2*n;i++){
113             ans+=tree[1].len2*(node[i].y-node[i-1].y);
114             l=findPos(node[i].l);
115             r=findPos(node[i].r)-1;
116             update(1, l, r, node[i].flag);
117         }
118         printf("%.2f
", ans);
119     }
120     return 0;
121 }