http://acm.hdu.edu.cn/showproblem.php?pid=1542
面积并
1 #include<bits/stdc++.h>
2 #define maxn 100005
3 #define lson l,mid,rt<<1
4 #define rson mid+1,r,rt<<1|1
5 #define pb push_back
6 using namespace std;
7
8 double tree[maxn<<2];
9 int lazy[maxn<<2];
10 vector<double>ve;
11
12 struct seg{
13 double l,r,h;
14 int flag;
15 seg(){}
16 seg(double _l,double _r,double _h,int _flag){
17 l=_l,r=_r,h=_h,flag=_flag;
18 }
19 bool operator<(const seg &b)const{
20 return h<b.h;
21 }
22 }s[maxn];
23
24 void push_up(int l,int r,int rt){
25 if(lazy[rt]){
26 tree[rt]=ve[r]-ve[l-1];
27 }
28 else if(l==r){
29 tree[rt]=0;
30 }
31 else{
32 tree[rt]=tree[rt<<1]+tree[rt<<1|1];
33 }
34 }
35
36 void build(int l,int r,int rt){
37 tree[rt]=0,lazy[rt]=0;
38 if(l==r) return;
39 int mid=l+r>>1;
40 build(lson);
41 build(rson);
42 }
43
44 void add(int L,int R,int v,int l,int r,int rt){
45 if(L<=l&&R>=r){
46 lazy[rt]+=v;
47 push_up(l,r,rt);
48 return;
49 }
50 int mid=l+r>>1;
51 if(L<=mid) add(L,R,v,lson);
52 if(R>mid) add(L,R,v,rson);
53 push_up(l,r,rt);
54 }
55
56 int getid(double x){
57 return lower_bound(ve.begin(),ve.end(),x)-ve.begin()+1;
58 }
59
60 int main(){
61 int n;
62 int Case=1;
63 while(~scanf("%d",&n)){
64 if(!n) break;
65 ve.clear();
66 int tot=0;
67 double x1,y1,x2,y2;
68 for(int i=1;i<=n;i++){
69 scanf("%lf %lf %lf %lf",&x1,&y1,&x2,&y2);
70 ve.pb(x1),ve.pb(x2);
71 s[++tot]=seg(x1,x2,y1,1);
72 s[++tot]=seg(x1,x2,y2,-1);
73 }
74 sort(ve.begin(),ve.end());
75 ve.erase(unique(ve.begin(),ve.end()),ve.end());
76 sort(s+1,s+tot+1);
77 int N=ve.size();
78 build(1,N,1);
79 double ans=0;
80 for(int i=1;i<tot;i++){
81 int L=getid(s[i].l);
82 int R=getid(s[i].r)-1;
83 add(L,R,s[i].flag,1,N,1);
84 ans+=tree[1]*(s[i+1].h-s[i].h);
85 }
86 printf("Test case #%d\n",Case++);
87 printf("Total explored area: %.2f\n\n",ans);
88 }
89 }
View Code
http://acm.hdu.edu.cn/showproblem.php?pid=1255
面积交
1 #include<bits/stdc++.h>
2 #define maxn 100005
3 #define lson l,mid,rt<<1
4 #define rson mid+1,r,rt<<1|1
5 #define pb push_back
6 using namespace std;
7
8 double tree[maxn<<2],tree2[maxn<<2];
9 int lazy[maxn<<2];
10 vector<double>ve;
11
12 struct seg{
13 double l,r,h;
14 int flag;
15 seg(){}
16 seg(double _l,double _r,double _h,int _flag){
17 l=_l,r=_r,h=_h,flag=_flag;
18 }
19 bool operator<(const seg &b)const{
20 return h<b.h;
21 }
22 }s[maxn];
23
24 void push_up(int l,int r,int rt){
25 if(lazy[rt]){
26 tree[rt]=ve[r]-ve[l-1];
27 }
28 else if(l==r){
29 tree[rt]=0;
30 }
31 else{
32 tree[rt]=tree[rt<<1]+tree[rt<<1|1];
33 }
34 }
35
36 void push_up2(int l,int r,int rt){
37 if(lazy[rt]>1){
38 tree2[rt]=ve[r]-ve[l-1];
39 }
40 else if(l==r){
41 tree2[rt]=0;
42 }
43 else if(lazy[rt]==1){
44 tree2[rt]=tree[rt<<1]+tree[rt<<1|1];
45 }
46 else{
47 tree2[rt]=tree2[rt<<1]+tree2[rt<<1|1];
48 }
49 }
50
51 void build(int l,int r,int rt){
52 tree[rt]=0,lazy[rt]=0;
53 if(l==r) return;
54 int mid=l+r>>1;
55 build(lson);
56 build(rson);
57 }
58
59 void add(int L,int R,int v,int l,int r,int rt){
60 if(L<=l&&R>=r){
61 lazy[rt]+=v;
62 push_up(l,r,rt);
63 push_up2(l,r,rt);
64 return;
65 }
66 int mid=l+r>>1;
67 if(L<=mid) add(L,R,v,lson);
68 if(R>mid) add(L,R,v,rson);
69 push_up(l,r,rt);
70 push_up2(l,r,rt);
71 }
72
73 int getid(double x){
74 return lower_bound(ve.begin(),ve.end(),x)-ve.begin()+1;
75 }
76
77 int main(){
78 int n;
79 int Case=1;
80 int T;
81 scanf("%d",&T);
82 while(T--){
83 scanf("%d",&n);
84 ve.clear();
85 int tot=0;
86 double x1,y1,x2,y2;
87 for(int i=1;i<=n;i++){
88 scanf("%lf %lf %lf %lf",&x1,&y1,&x2,&y2);
89 ve.pb(x1),ve.pb(x2);
90 s[++tot]=seg(x1,x2,y1,1);
91 s[++tot]=seg(x1,x2,y2,-1);
92 }
93 sort(ve.begin(),ve.end());
94 ve.erase(unique(ve.begin(),ve.end()),ve.end());
95 sort(s+1,s+tot+1);
96 int N=ve.size();
97 build(1,N,1);
98 double ans=0;
99 for(int i=1;i<tot;i++){
100 int L=getid(s[i].l);
101 int R=getid(s[i].r)-1;
102 add(L,R,s[i].flag,1,N,1);
103 ans+=tree2[1]*(s[i+1].h-s[i].h);
104 }
105 printf("%.2f\n",ans);
106 }
107 }
View Code