摘要：
id=1151题目：题意：求所有矩形的面积，重合部分只算一次。思路：扫描线入门题，推荐几篇学扫描线的博客：1.http://www.cnblogs.com/scau20110726/archive/2013/04/12/3016765.html2.https://blog.csdn.net/qq_38786088/article/details/786334783.https://blog.csdn.net/lwt36/article/details/48908031（强烈推荐！
题目链接：http://poj.org/problem?id=1151
题目：
题意：求所有矩形的面积，重合部分只算一次。
思路：扫描线入门题，推荐几篇学扫描线的博客：
1.http://www.cnblogs.com/scau20110726/archive/2013/04/12/3016765.html
2.https://blog.csdn.net/qq_38786088/article/details/78633478
3.https://blog.csdn.net/lwt36/article/details/48908031（强烈推荐！）
代码实现如下：
1 #include <set> 2 #include <map> 3 #include <queue> 4 #include <stack> 5 #include <cmath> 6 #include <bitset> 7 #include <cstdio> 8 #include <string> 9 #include <vector> 10 #include <cstdlib> 11 #include <cstring> 12 #include <iostream> 13 #include <algorithm> 14 using namespacestd; 15 16 typedef long longll; 17 typedef unsigned long longull; 18 19 #define lson i<<1,l,mid 20 #define rson i<<1|1,mid+1,r 21 #define bug printf("********* "); 22 #define FIN freopen("D://code//in.txt", "r", stdin); 23 #define debug(x) cout<<"["<<x<<"]" <<endl; 24 #define IO ios::sync_with_stdio(false),cin.tie(0); 25 26 const double eps = 1e-8; 27 const int mod = 10007; 28 const int maxn = 200 + 7; 29 const double pi = acos(-1); 30 const int inf = 0x3f3f3f3f; 31 const ll INF = 0x3f3f3f3f3f3f3f3f; 32 33 inline int read() {//读入挂 34 int ret = 0, c, f = 1; 35 for(c = getchar(); !(isdigit(c) || c == '-'); c =getchar()); 36 if(c == '-') f = -1, c =getchar(); 37 for(; isdigit(c); c = getchar()) ret = ret * 10 + c - '0'; 38 if(f < 0) ret = -ret; 39 returnret; 40 } 41 42 intn, t; 43 doublex1, y_1, x2, y_2; 44 double y[1007]; 45 46 structLine { 47 doubley1, y2, x; 48 intflag; 49 bool operator < (const Line& a) const{ 50 return x <a.x; 51 } 52 }line[305]; 53 54 structnode { 55 intl, r, cover; 56 doublelf, rf, len; 57 }segtree[maxn*4]; 58 59 void push_up(inti) { 60 if(segtree[i].cover > 0) { 61 segtree[i].len = segtree[i].rf -segtree[i].lf; 62 } else if(segtree[i].l + 1 ==segtree[i].r) { 63 segtree[i].len = 0; 64 } else{ 65 segtree[i].len = segtree[i*2].len + segtree[i*2+1].len; 66 } 67 } 68 69 void build(int i, int l, intr) { 70 segtree[i].l = l, segtree[i].r =r; 71 segtree[i].lf = y[l], segtree[i].rf =y[r]; 72 segtree[i].cover = segtree[i].len = 0; 73 if(l + 1 == r) return; 74 int mid = (l + r) >> 1; 75 build(i * 2, l, mid); 76 build(i * 2 + 1, mid, r); 77 } 78 79 void update(int i, double l, double r, intflag) { 80 if(segtree[i].lf == l && segtree[i].rf ==r) { 81 segtree[i].cover +=flag; 82 push_up(i); 83 return; 84 } 85 if(l >= segtree[i * 2 + 1].lf) { 86 update(i * 2 + 1, l, r, flag); 87 } else if(r <= segtree[i * 2].rf) { 88 update(i * 2, l, r, flag); 89 } else{ 90 update(i * 2, l, segtree[i*2].rf, flag); 91 update(i * 2 + 1, segtree[i*2+1].lf, r, flag); 92 } 93 push_up(i); 94 } 95 96 intmain() { 97 //FIN; 98 int icase = 0; 99 while(~scanf("%d", &n) &&n) { 100 t = 1; 101 printf("Test case #%d ", ++icase); 102 for(int i = 1; i <= n; i++,t++) { 103 scanf("%lf%lf%lf%lf", &x1, &y_1, &x2, &y_2); 104 line[t].x =x1; 105 line[t].y1 =y_1; 106 line[t].y2 =y_2; 107 line[t].flag = 1; 108 y[t] =y_1; 109 line[++t].x =x2; 110 line[t].y1 =y_1; 111 line[t].y2 =y_2; 112 line[t].flag = -1; 113 y[t] =y_2; 114 } 115 sort(line + 1, line +t); 116 sort(y + 1, y +t); 117 build(1, 1, t - 1); 118 double ans = 0; 119 update(1, line[1].y1, line[1].y2, line[1].flag); 120 for(int i = 2; i < t; i++) { 121 ans += segtree[1].len * (line[i].x - line[i-1].x); 122 update(1, line[i].y1, line[i].y2, line[i].flag); 123 } 124 printf("Total explored area: %.2f ", ans); 125 } 126 return 0; 127 }