hdu 1542 线扫描+线段树(离散化) 求覆盖面积/周长

// hdu1542 

// 线扫瞄思想结合线段树求覆盖面积问题，也能求周长。具体如何线扫瞄 下面参考博客里面有

// 直接百度学的(想破脑壳也只能是wa或者tle)

// 参考博客  HDU 1542 Atlantis(线段树:扫描线)

// 不能算抄。。。结合了多方代码得出我喜欢的写法。。。离散化区间问题只停留在听懂的层面上, 之前并查集区间离散化也是囫囵吞枣的学,不能这样啊( ఠൠఠ )ﾉ

 1 #include<cstdio>
 2 #include<algorithm>
 3 #define L k<<1
 4 #define R k<<1|1
 5 #define mid (tree[k].l+tree[k].r)>>1
 6 using namespace std;
 7 typedef long long ll;
 8 const int MAXN = 200+5;
 9 
10 double X[MAXN];
11 struct Edge {
12     double l, r;
13     double h;
14     int f;
15     Edge() {}
16     Edge(double l, double r, double h, int f):l(l),r(r),h(h),f(f) {}
17     bool operator < (const Edge &a) const {
18         return h < a.h;
19     }
20 }edge[MAXN];
21 //Edge ;
22 
23 struct segmemt_tree {
24     int l, r;// 左右区间端点
25     int cover;
26     double len;
27 }tree[4*MAXN+1];
28 
29 inline void build(int k, int l, int r) {
30     tree[k].l = l; tree[k].r = r;
31     tree[k].cover = tree[k].len = 0;
32     if(l == r) return ;
33     int m = mid;
34     build(L, l, m);
35     build(R, m+1, r);
36 }
37 
38 inline void push_up(int k) {
39     if(tree[k].cover) tree[k].len = X[tree[k].r+1] - X[tree[k].l];
40     else if(tree[k].l == tree[k].r) tree[k].len = 0;
41     else tree[k].len = tree[L].len + tree[R].len;
42 }
43 
44 inline void update(int k, int x, int y, int cover) {
45     if(tree[k].l >= x && tree[k].r <= y) {
46         tree[k].cover += cover;
47         push_up(k);
48         return ;
49     }
50     int m = mid;
51     if(x <= m) update(L, x, y, cover);
52     if(y > m) update(R, x, y, cover);
53     push_up(k);
54 }
55 
56 int main() {
57     int n, Case = 0;
58     while(scanf("%d", &n) == 1 && n) {
59         int cnt = 0;
60         double x1, y1, x2, y2;
61         for(int i = 0; i != n; ++i) {
62             scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
63             X[cnt] = x1;
64             edge[cnt++] = Edge(x1, x2, y1, 1);
65             X[cnt] = x2;
66             edge[cnt++] = Edge(x1, x2, y2, -1);
67         }
68         sort(X, X+cnt);
69         sort(edge, edge+cnt);
70         int k = unique(X, X+cnt) - X;
71         build(1, 0, k-1);
72         double sum = 0;
73         for(int i = 0; i != cnt; ++i) {
74             int l = lower_bound(X, X+k, edge[i].l) - X;
75             int r = lower_bound(X, X+k, edge[i].r) - X - 1;
76             update(1, l, r, edge[i].f);
77             sum += (edge[i+1].h - edge[i].h) * tree[1].len;
78         }
79         printf("Test case #%d
", ++Case);
80         printf("Total explored area: %.2lf

", sum);
81     }
82     return 0;
83 }

// hdu 1255上一题升级版(求覆盖两次和两次以上的面积)

 1 /*
 2  * @Author: pupil-XJ
 3  * @Date: 2019-10-10 00:09:46
 4  * @LastEditTime: 2019-10-10 11:47:20
 5  */
 6 #include<cstdio>
 7 #include<algorithm>
 8 #define L k<<1
 9 #define R k<<1|1
10 #define mid (tree[k].l+tree[k].r)>>1
11 using namespace std;
12 const int MAXN = 2000+5;
13 
14 double x[MAXN];
15 struct Edge {
16     double l, r, h;
17     int f;
18     Edge(){}
19     Edge(double l, double r, double h, int f):l(l),r(r),h(h),f(f){}
20     bool operator < (const Edge &a) const {
21         return h < a.h;
22     }
23 } edge[MAXN];
24 
25 struct segmemt_tree {
26     int l, r, cover;
27     double len1, len2;// len1(cover once) len2(cover over than once)
28 } tree[4*MAXN+1];
29 
30 inline void build(int k, int l, int r) {
31     tree[k].l = l; tree[k].r = r;
32     tree[k].cover = tree[k].len1 = tree[k].len2 = 0;
33     if(l == r) return ;
34     int m = mid;
35     build(L, l, m);
36     build(R, m+1, r);
37 }
38 
39 inline void push_up(int k) {
40     // update->len1
41     if(tree[k].cover) tree[k].len1 = x[tree[k].r+1] - x[tree[k].l];
42     else if(tree[k].l == tree[k].r) tree[k].len1 = 0;
43     else tree[k].len1 = tree[L].len1 + tree[R].len1;
44     // update->len2
45     if(tree[k].cover > 1) tree[k].len2 = x[tree[k].r+1] - x[tree[k].l];
46     else if(tree[k].l == tree[k].r) tree[k].len2 = 0;
47     else if(tree[k].cover == 1) tree[k].len2 = tree[L].len1 + tree[R].len1;
48     else tree[k].len2 = tree[L].len2 + tree[R].len2;
49 }
50 
51 inline void update(int k, int x, int y, int f) {
52     if(tree[k].l >= x && tree[k].r <= y) {
53         tree[k].cover += f;
54         push_up(k);
55         return ;
56     }
57     int m = mid;
58     if(x <= m) update(L, x, y, f);
59     if(y > m) update(R, x, y, f);
60     push_up(k);
61 }
62 
63 int main() {
64     int T, n;
65     double x1, y1, x2, y2;
66     scanf("%d", &T);
67     while(T--) {
68         scanf("%d", &n);
69         int cnt = 0;
70         for(int i = 0; i != n; ++i) {
71             scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
72             x[cnt] = x1;
73             edge[cnt++] = Edge(x1, x2, y1, 1);
74             x[cnt] = x2;
75             edge[cnt++] = Edge(x1, x2, y2, -1);
76         }
77         sort(x, x+cnt);
78         sort(edge, edge+cnt);
79         int k = unique(x, x+cnt) - x;
80         
81         build(1, 0, k-1);
82         double sum = 0;
83         for(int i = 0; i != cnt; ++i) {
84             int l = lower_bound(x, x+k, edge[i].l) - x;
85             int r = lower_bound(x, x+k, edge[i].r) - x - 1;
86             update(1, l, r, edge[i].f);
87             sum += (edge[i+1].h - edge[i].h) * tree[1].len2;
88         }
89         printf("%.2lf
", sum);
90     }
91     return 0;
92 }
View Code

 // poj 1177 求覆盖周长

推荐博客: ->。

 1 #include<cstdio>
 2 #include<cmath>
 3 #include<algorithm>
 4 #define L k<<1
 5 #define R k<<1|1
 6 #define mid (tree[k].l+tree[k].r)>>1
 7 using namespace std;
 8 const int MAXN = 10000+5;
 9 
10 int x[MAXN];
11 struct Edge {
12     int l, r, h;
13     int f;
14     Edge(){}
15     Edge(int l, int r, int h, int f):l(l),r(r),h(h),f(f){}
16     bool operator < (const Edge &a) const {
17         return h < a.h;
18     }
19 } edge[MAXN];
20 
21 struct segmemt_tree {
22     int l, r, cover, num;
23     int lc, rc;
24     int len;
25 } tree[4*MAXN+1];
26 
27 inline void build(int k, int l, int r) {
28     tree[k].l = l; tree[k].r = r;
29     tree[k].cover = tree[k].num = tree[k].lc = tree[k].rc = tree[k].len = 0;
30     if(l == r) return;
31     int m = mid;
32     build(L, l, m);
33     build(R, m+1, r);
34 }
35 
36 inline void push_up(int k) {
37     if(tree[k].cover) {
38         tree[k].len = x[tree[k].r+1] - x[tree[k].l];
39         tree[k].lc = tree[k].rc = 1;
40         tree[k].num = 1;
41     }
42     else if(tree[k].l == tree[k].r) {
43         tree[k].len = 0;
44         tree[k].lc = tree[k].rc = 0;
45         tree[k].num = 0;
46     }
47     else {
48         tree[k].len = tree[L].len + tree[R].len;
49         tree[k].lc = tree[L].lc; tree[k].rc = tree[R].rc;
50         tree[k].num = tree[L].num + tree[R].num - (tree[L].rc&tree[R].lc);
51     }
52 }
53 
54 inline void update(int k, int x, int y, int f) {
55     if(tree[k].l >= x && tree[k].r <= y) {
56         tree[k].cover += f;
57         push_up(k);
58         return ;
59     }
60     int m = mid;
61     if(x <= m) update(L, x, y, f);
62     if(y > m) update(R, x, y, f);
63     push_up(k);
64 }
65 
66 int main() {
67     int n, cnt = 0;
68     scanf("%d", &n);
69     int x1, x2, y1, y2;
70     for(int i = 0; i != n; ++i) {
71         scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
72         x[cnt] = x1;
73         edge[cnt++] = Edge(x1, x2, y1, 1);
74         x[cnt] = x2;
75         edge[cnt++] = Edge(x1, x2, y2, -1);
76     }
77     sort(x, x+cnt);
78     sort(edge, edge+cnt);
79     int k = unique(x, x+cnt) - x;
80 
81     build(1, 0, k-1);
82     int sum = 0, last = 0;
83     for(int i = 0; i != cnt; ++i) {
84         int l = lower_bound(x, x+k, edge[i].l) - x;
85         int r = lower_bound(x, x+k, edge[i].r) - x - 1;
86         update(1, l, r, edge[i].f);
87         sum += abs(tree[1].len - last);
88         sum += (edge[i+1].h - edge[i].h)*2*tree[1].num;
89         last = tree[1].len;
90     }
91     printf("%d
", sum);
92     return 0;
93 }

12ewqewqeqweewqqwe

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/pupil-xj/p/11643843.html