覆盖的面积

  1 /*************************************************************************  2     > File Name: G.cpp  3     > Author: Stomach_ache  4     > Mail: sudaweitong@gmail.com  5     > Created Time: 2014年07月26日 星期六 19时05分05秒  6     > Propose: hdu 1542  7  ************************************************************************/  8 #include <cmath>  9 #include <string> 10 #include <cstdio> 11 #include <fstream> 12 #include <cstring> 13 #include <iostream> 14 #include <algorithm> 15 using namespace std; 16  17 const int maxn = 1100; 18 struct Line { 19       double x, y1, y2; 20     int cover; 21     friend bool operator < (Line a, Line b) { 22           return a.x < b.x; 23     } 24 }line[maxn*2 + 5]; 25  26 struct node { 27       double x, y1, y2; 28     int cover, flag; 29 }Tree[maxn*1000]; 30 int n; 31 double y[maxn*2]; 32  33 void build(int root, int L, int R) { 34       Tree[root].x = -1; 35       Tree[root].cover = 0; 36     Tree[root].y1 = y[L]; 37     Tree[root].y2 = y[R]; 38     Tree[root].flag = 0; 39       if (R - L == 1) { 40           Tree[root].flag = 1; 41         return ; 42     } 43     int M = (L + R) / 2; 44     build(root * 2, L, M); 45     build(root * 2 + 1, M, R); 46 } 47  48 double insert(int root, Line &ll) { 49       if (Tree[root].y1 >= ll.y2 || Tree[root].y2 <= ll.y1) { 50           return 0.0; 51     } 52     if (Tree[root].flag) { 53           if (Tree[root].cover > 1) { 54             double ans = (ll.x - Tree[root].x) * (Tree[root].y2 - Tree[root].y1); 55             Tree[root].x = ll.x; 56               Tree[root].cover += ll.cover; 57             return ans; 58         } else { 59               Tree[root].cover += ll.cover; 60             Tree[root].x = ll.x; 61             return 0.0; 62         } 63     } 64     double ans1 = insert(root * 2, ll); 65     double ans2 = insert(root * 2 + 1, ll); 66     return ans1 + ans2; 67 } 68  69 int main(void) { 70 #ifndef ONLINE_JUDGE 71       freopen("in.txt", "r", stdin); 72 #endif 73       int cas; 74     scanf("%d", &cas); 75       while (cas--) { 76         scanf("%d", &n);  77           int cnt = 0; 78           for (int i = 0; i < n; i++) { 79              double xx, yy, xxx, yyy; 80             scanf("%lf %lf %lf %lf", &xx, &yy, &xxx, &yyy); 81             y[++cnt] = yy; 82             line[cnt].x = xx; line[cnt].y1 = yy; line[cnt].y2 = yyy; 83             line[cnt].cover = 1; 84             y[++cnt] = yyy; 85             line[cnt].x = xxx; line[cnt].y1 = yy; line[cnt].y2 = yyy; 86             line[cnt].cover = -1; 87         } 88         sort(y + 1, y + cnt + 1); 89         int len = 1; 90         for (int i = 2; i <= cnt; i++) { 91               if (y[i] != y[len]) { 92                   y[++len] = y[i]; 93             } 94         } 95         sort(line + 1, line + cnt + 1); 96         build(1, 1, len); 97         double ans = 0.0; 98         for (int i = 1; i <= cnt; i++) { 99               ans += insert(1, line[i]);100         }101         printf("%.2f\n", ans);102     }103 104     return 0;105 }

第二种做法效率较高。

  1 /*************************************************************************  2     > File Name: G.cpp  3     > Author: Stomach_ache  4     > Mail: sudaweitong@gmail.com  5     > Created Time: 2014年07月26日 星期六 19时05分05秒  6     > Propose: hdu   7  ************************************************************************/  8 #include <map>  9 #include <cmath> 10 #include <string> 11 #include <cstdio> 12 #include <vector> 13 #include <fstream> 14 #include <cstring> 15 #include <iostream> 16 #include <algorithm> 17 using namespace std; 18  19 const int maxn = 1100; 20 //保存每条线段的信息 21 struct Line { 22       double x, y1, y2; 23     //矩形的左边或者右边 24     int flag; 25     friend bool operator < (Line a, Line b) { 26           return a.x < b.x; 27     } 28 }line[maxn*2 + 5]; 29  30 //线段树结点信息 31 struct node { 32       int l, r; 33     //线段被覆盖的次数 34     int cover; 35     //len为被覆盖一次的长度，len2为被覆盖两次的长度 36     double len, len2; 37 }Tree[maxn*40]; 38 int n; 39 //保存所有y轴坐标 40 double y[maxn*2]; 41 //离散化使用 42 vector<double> xs; 43  44 void build(int root, int L, int R) { 45       Tree[root].l = L; 46     Tree[root].r = R; 47       Tree[root].len = 0.0; 48     Tree[root].len2 = 0.0; 49       Tree[root].cover = 0; 50       if (R - L == 1) { 51         return ; 52     } 53     int M = (L + R) / 2; 54     build(root * 2, L, M); 55     build(root * 2 + 1, M, R); 56 } 57  58 void pushup(int root) { 59       //被覆盖两次以上 60     if (Tree[root].cover > 1) { 61           Tree[root].len = 0; 62           Tree[root].len2 = xs[Tree[root].r-1] - xs[Tree[root].l-1]; 63     } else if (Tree[root].cover == 1) { //被覆盖一次 64         Tree[root].len2 = Tree[root*2].len + Tree[root*2+1].len 65                            +Tree[root*2].len2 + Tree[root*2+1].len2; 66           Tree[root].len = xs[Tree[root].r-1] - xs[Tree[root].l-1] 67                            - Tree[root].len2; 68     } else { //没有被覆盖 69          if (Tree[root].l + 1 == Tree[root].r) 70             Tree[root].len = Tree[root].len2 = 0.0; 71         else { 72             Tree[root].len = Tree[root*2].len + Tree[root*2+1].len; 73             Tree[root].len2 = Tree[root*2].len2 + Tree[root*2+1].len2; 74         } 75     } 76 } 77  78 void update(int root, int L, int R, int flag) { 79       //不在当前区间内 80       if (Tree[root].l >= R || Tree[root].r <= L)  81           return ; 82     //包含在当前区间内 83       if (Tree[root].l >= L && Tree[root].r <= R) { 84         Tree[root].cover += flag; 85           pushup(root); 86           return ; 87     } 88     int M = (Tree[root].l + Tree[root].r) / 2; 89     update(root*2, L, R, flag); 90     update(root*2+1, L, R, flag); 91     pushup(root); 92 } 93  94 //离散化 95 int compress(int m) { 96       xs.clear(); 97     for (int i = 1; i <= m; i++) xs.push_back(y[i]); 98     sort(xs.begin(), xs.end()); 99     xs.erase(unique(xs.begin(), xs.end()), xs.end());100     return xs.size();101 }102 103 104 int main(void) {105 #ifndef ONLINE_JUDGE106       freopen("in.txt", "r", stdin);107 #endif108       int cas;109     scanf("%d", &cas);110       while (cas--) {111           scanf("%d", &n);112           int cnt = 0;113           for (int i = 0; i < n; i++) {114              double xx, yy, xxx, yyy;115             scanf("%lf %lf %lf %lf", &xx, &yy, &xxx, &yyy);116             y[++cnt] = yy;117             line[cnt].x = xx; line[cnt].y1 = yy; line[cnt].y2 = yyy;118             line[cnt].flag = 1;119             y[++cnt] = yyy;120             line[cnt].x = xxx; line[cnt].y1 = yy; line[cnt].y2 = yyy;121             line[cnt].flag = -1;122         }123         int w = compress(cnt);124         sort(line + 1, line + cnt + 1);125         build(1, 1, cnt);126         double ans = 0.0;127         int l = find(xs.begin(), xs.end(), line[1].y1) - xs.begin() + 1;128         int r = find(xs.begin(), xs.end(), line[1].y2) - xs.begin() + 1;129         update(1, l, r, line[1].flag);130         for (int i = 2; i <= cnt; i++) {131               int l = find(xs.begin(), xs.end(), line[i].y1) - xs.begin() + 1;132             int r = find(xs.begin(), xs.end(), line[i].y2) - xs.begin() + 1;133             ans += (line[i].x - line[i-1].x) * Tree[1].len2;134               update(1, l, r, line[i].flag);135         }136         printf("%.2f\n", ans);137     }138 139     return 0;140 }