我是靠谱客的博主 结实小熊猫，这篇文章主要介绍Atlantis HDU - 1542 + 覆盖的面积 HDU - 1255 + Picture HDU - 1828，现在分享给大家，希望可以做个参考。
点击打开链接
点击打开链接
点击打开链接
扫描线求矩形面积的并与交 这类问题之前一直都是更新到底 数据稍强就会T
求周长会用到区间合并
详解点击打开链接
存模板
hdu1542
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110#include <cstdio> #include <cstring> #include <algorithm> using namespace std; struct node1 { double l; double r; double h; int f; }; struct node2 { double l; double r; double val; int f; int leaf; }; node1 line[100010]; node2 tree[800010]; double pre[200010]; int n; bool cmp(node1 n1,node1 n2) { return n1.h<n2.h; } void build(int l,int r,int cur) { int m; tree[cur].l=pre[l]; tree[cur].r=pre[r]; tree[cur].val=0; tree[cur].f=0; tree[cur].leaf=0; if(l+1==r) { tree[cur].leaf=1; return; } m=(l+r)/2; build(l,m,cur*2); build(m,r,cur*2+1); return; } void pushup(int cur) { if(tree[cur].f>0) { tree[cur].val=tree[cur].r-tree[cur].l; } else { if(tree[cur].leaf) tree[cur].val=0; else tree[cur].val=tree[2*cur].val+tree[2*cur+1].val; } return; } void scan(double pl,double pr,int f,int cur) { if(pl<=tree[cur].l&&tree[cur].r<=pr) { tree[cur].f+=f; pushup(cur); return; } if(pl<tree[cur*2].r) scan(pl,pr,f,cur*2); if(pr>tree[cur*2+1].l) scan(pl,pr,f,cur*2+1); pushup(cur); return; } int main() { double ans,x1,y1,x2,y2; int i,j,cas; cas=1; while(scanf("%d",&n)!=EOF) { if(n==0) break; for(i=1;i<=n;i++) { scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2); line[2*i-1].l=x1,line[2*i-1].r=x2,line[2*i-1].h=y1,line[2*i-1].f=1; line[2*i].l=x1,line[2*i].r=x2,line[2*i].h=y2,line[2*i].f=-1; pre[2*i-1]=x1,pre[2*i]=x2; } sort(line+1,line+2*n+1,cmp); sort(pre+1,pre+2*n+1); for(i=1,j=0;i<=2*n;i++) { if(j==0||pre[i]!=pre[j]) { j++; pre[j]=pre[i]; } } build(1,j,1); scan(line[1].l,line[1].r,line[1].f,1); ans=0; for(i=2;i<=2*n;i++) { ans+=tree[1].val*(line[i].h-line[i-1].h); scan(line[i].l,line[i].r,line[i].f,1); } printf("Test case #%dn",cas++); printf("Total explored area: %.2fnn",ans); } return 0; }
hdu1255
复制代码
1
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124#include <cstdio> #include <cstring> #include <algorithm> using namespace std; struct node1 { double l; double r; double h; int f; }; struct node2 { double l; double r; double val1; double val2; int f; int leaf; }; node1 line[2010]; node2 tree[8010]; double pre[2010]; int n; bool cmp(node1 n1,node1 n2) { return n1.h<n2.h; } void build(int l,int r,int cur) { int m; tree[cur].l=pre[l]; tree[cur].r=pre[r]; tree[cur].val1=0; tree[cur].val2=0; tree[cur].f=0; tree[cur].leaf=0; if(l+1==r) { tree[cur].leaf=1; return; } m=(l+r)/2; build(l,m,cur*2); build(m,r,cur*2+1); return; } void pushup(int cur) { if(tree[cur].f>1) { tree[cur].val1=tree[cur].val2=tree[cur].r-tree[cur].l; } else if(tree[cur].f==1) { tree[cur].val1=tree[cur].r-tree[cur].l; if(tree[cur].leaf) tree[cur].val2=0; else tree[cur].val2=tree[cur*2].val1+tree[cur*2+1].val1; } else { if(tree[cur].leaf) { tree[cur].val1=tree[cur].val2=0; } else { tree[cur].val1=tree[cur*2].val1+tree[cur*2+1].val1; tree[cur].val2=tree[cur*2].val2+tree[cur*2+1].val2; } } return; } void scan(double pl,double pr,int f,int cur) { if(pl<=tree[cur].l&&tree[cur].r<=pr) { tree[cur].f+=f; pushup(cur); return; } if(pl<tree[cur*2].r) scan(pl,pr,f,cur*2); if(pr>tree[cur*2+1].l) scan(pl,pr,f,cur*2+1); pushup(cur); return; } int main() { double ans,x1,y1,x2,y2; int t,cas,i,j; scanf("%d",&t); for(cas=1;cas<=t;cas++) { scanf("%d",&n); for(i=1;i<=n;i++) { scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2); line[2*i-1].l=x1,line[2*i-1].r=x2,line[2*i-1].h=y1,line[2*i-1].f=1; line[2*i].l=x1,line[2*i].r=x2,line[2*i].h=y2,line[2*i].f=-1; pre[2*i-1]=x1,pre[2*i]=x2; } sort(line+1,line+2*n+1,cmp); sort(pre+1,pre+2*n+1); for(i=1,j=0;i<=2*n;i++) { if(j==0||pre[i]!=pre[j]) { j++; pre[j]=pre[i]; } } build(1,j,1); scan(line[1].l,line[1].r,line[1].f,1); ans=0; for(i=2;i<=2*n;i++) { ans+=tree[1].val2*(line[i].h-line[i-1].h); scan(line[i].l,line[i].r,line[i].f,1); } printf("%.2fn",ans); } return 0; }
hdu1828
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120#include <bits/stdc++.h> using namespace std; struct node1 { int l; int r; int h; int f; }; struct node2 { int l; int r; int f; int val; int left; int right; int all; int leaf; }; node1 line[10010]; node2 tree[40010]; int pre[10010]; int n; bool cmp(node1 n1,node1 n2) { return n1.h<n2.h; } void pushup(int cur) { if(tree[cur].f>0) { tree[cur].val=tree[cur].r-tree[cur].l; tree[cur].all=tree[cur].left=tree[cur].right=1; } else if(tree[cur].leaf) { tree[cur].val=0; tree[cur].all=tree[cur].left=tree[cur].right=0; } else { tree[cur].val=tree[2*cur].val+tree[2*cur+1].val; tree[cur].left=tree[2*cur].left; tree[cur].right=tree[2*cur+1].right; tree[cur].all=tree[2*cur].all+tree[2*cur+1].all-tree[2*cur].right*tree[2*cur+1].left; } return; } void build(int l,int r,int cur) { int m; tree[cur].l=pre[l]; tree[cur].r=pre[r]; tree[cur].f=0; tree[cur].val=0; tree[cur].left=0; tree[cur].right=0; tree[cur].all=0; tree[cur].leaf=0; if(l+1==r) { tree[cur].leaf=1; return; } m=(l+r)/2; build(l,m,2*cur); build(m,r,2*cur+1); return; } void update(int pl,int pr,int f,int cur) { if(pl<=tree[cur].l&&tree[cur].r<=pr) { tree[cur].f+=f; pushup(cur); return; } if(pl<tree[2*cur].r) update(pl,pr,f,2*cur); if(pr>tree[2*cur+1].l) update(pl,pr,f,2*cur+1); pushup(cur); return; } int main() { int i,j,x1,y1,x2,y2,tem,ans; while(scanf("%d",&n)!=EOF) { for(i=1;i<=n;i++) { scanf("%d%d%d%d",&x1,&y1,&x2,&y2); line[2*i-1].l=x1,line[2*i-1].r=x2,line[2*i-1].h=y1,line[2*i-1].f=1; line[2*i].l=x1,line[2*i].r=x2,line[2*i].h=y2,line[2*i].f=-1; pre[2*i-1]=x1,pre[2*i]=x2; } sort(line+1,line+2*n+1,cmp); sort(pre+1,pre+2*n+1); for(i=1,j=0;i<=2*n;i++) { if(j==0||pre[j]!=pre[i]) { pre[++j]=pre[i]; } } build(1,j,1); tem=0,ans=0; for(i=1;i<=2*n-1;i++) { update(line[i].l,line[i].r,line[i].f,1); ans+=abs(tree[1].val-tem); tem=tree[1].val; ans+=2*tree[1].all*(line[i+1].h-line[i].h); } update(line[i].l,line[i].r,line[i].f,1); ans+=abs(tree[1].val-tem); printf("%dn",ans); } return 0; }
最后
以上就是结实小熊猫最近收集整理的关于Atlantis HDU - 1542 + 覆盖的面积 HDU - 1255 + Picture HDU - 1828的全部内容，更多相关Atlantis内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复