题目链接：https://vjudge.net/problem/HDU-1542
InputThe input file consists of several test cases. Each test case starts with a line containing a single integer n (1<=n<=100) of available maps. The n following lines describe one map each. Each of these lines contains four numbers x1;y1;x2;y2 (0<=x1<x2<=100000;0<=y1<y2<=100000), not necessarily integers. The values (x1; y1) and (x2;y2) are the coordinates of the top-left resp. bottom-right corner of the mapped area.
The input file is terminated by a line containing a single 0. Don’t process it.OutputFor each test case, your program should output one section. The first line of each section must be “Test case #k”, where k is the number of the test case (starting with 1). The second one must be “Total explored area: a”, where a is the total explored area (i.e. the area of the union of all rectangles in this test case), printed exact to two digits to the right of the decimal point.
Output a blank line after each test case.
Sample Input
2 10 10 20 20 15 15 25 25.5 0
Sample Output
Test case #1 Total explored area: 180.00
题解：
写法一：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <algorithm> 6 #include <vector> 7 #include <queue> 8 #include <stack> 9 #include <map> 10 #include <string> 11 #include <set> 12 using namespace std; 13 typedef long long LL; 14 const double EPS = 1e-8; 15 const int INF = 2e9; 16 const LL LNF = 2e18; 17 const int MAXN = 1e5+10; 18 19 struct line 20 { 21 double le, ri, h; 22 int id; 23 bool operator<(const line &a){ 24 return h<a.h; 25 } 26 }Line[MAXN]; 27 28 double sum[MAXN<<2], addv[MAXN<<2]; 29 double X[MAXN]; 30 31 void push_up(int u, int l, int r) 32 { 33 if(addv[u]>=1) sum[u] = X[r] - X[l]; 34 else sum[u] = (l+1==r)?0:sum[u*2]+sum[u*2+1]; 35 } 36 37 void add(int u, int l, int r, int x, int y, int v) 38 { 39 if(x<=l && r<=y) 40 { 41 addv[u] += v; 42 push_up(u, l, r); 43 return; 44 } 45 46 int mid = (l+r)>>1; 47 if(x<=mid-1) add(u*2, l, mid, x, y, v); 48 if(y>=mid+1) add(u*2+1, mid, r, x, y, v); 49 push_up(u, l, r); 50 } 51 52 int main() 53 { 54 int n, kase = 0; 55 while(scanf("%d", &n) && n) 56 { 57 for(int i = 1; i<=n; i++) 58 { 59 double x1, y1, x2, y2; 60 scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2); 61 Line[i].le = Line[i+n].le = x1; 62 Line[i].ri = Line[i+n].ri = x2; 63 Line[i].h = y1; Line[i+n].h = y2; 64 Line[i].id = 1; Line[i+n].id = -1; 65 X[i] = x1; X[i+n] = x2; 66 } 67 68 sort(Line+1, Line+1+2*n); 69 sort(X+1, X+1+2*n); 70 int m = unique(X+1, X+1+2*n) - (X+1); 71 72 memset(sum, 0, sizeof(sum)); 73 memset(addv, 0, sizeof(addv)); 74 double ans = 0; 75 for(int i = 1; i<=2*n-1; i++) 76 { 77 int l = upper_bound(X+1, X+1+m, Line[i].le) - (X+1); 78 int r = upper_bound(X+1, X+1+m, Line[i].ri) - (X+1); 79 add(1, 1, m, l, r, Line[i].id); 80 ans += sum[1]* (Line[i+1].h-Line[i].h); 81 } 82 printf("Test case #%d\n", ++kase); 83 printf("Total explored area: %.2f\n\n", ans); 84 } 85 }
写法二：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <algorithm> 6 #include <vector> 7 #include <queue> 8 #include <stack> 9 #include <map> 10 #include <string> 11 #include <set> 12 using namespace std; 13 typedef long long LL; 14 const double EPS = 1e-8; 15 const int INF = 2e9; 16 const LL LNF = 2e18; 17 const int MAXN = 1e5+10; 18 19 struct line 20 { 21 double le, ri, h; 22 int id; 23 bool operator<(const line &a){ 24 return h<a.h; 25 } 26 }Line[MAXN]; 27 28 double sum[MAXN<<2], addv[MAXN<<2]; 29 double X[MAXN]; 30 31 void push_up(int u, int l, int r) //区间左闭右开 32 { 33 if(addv[u]) sum[u] = X[r+1] - X[l]; 34 else sum[u] = (l==r)?0:(sum[u*2]+sum[u*2+1]); 35 } 36 37 void add(int u, int l, int r, int x, int y, int v) 38 { 39 if(x<=l && r<=y) 40 { 41 addv[u] += v; 42 push_up(u, l, r); 43 return; 44 } 45 46 int mid = (l+r)>>1; 47 if(x<=mid) add(u*2, l, mid, x, y, v); 48 if(y>=mid+1) add(u*2+1, mid+1, r, x, y, v); 49 push_up(u, l, r); 50 } 51 52 int main() 53 { 54 int n, kase = 0; 55 while(scanf("%d", &n) && n) 56 { 57 for(int i = 1; i<=n; i++) 58 { 59 double x1, y1, x2, y2; 60 scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2); 61 Line[i].le = Line[i+n].le = x1; 62 Line[i].ri = Line[i+n].ri = x2; 63 Line[i].h = y1; Line[i+n].h = y2; 64 Line[i].id = 1; Line[i+n].id = -1; 65 X[i] = x1; X[i+n] = x2; 66 } 67 68 sort(Line+1, Line+1+2*n); 69 sort(X+1, X+1+2*n); 70 int m = unique(X+1, X+1+2*n) - (X+1); 71 72 memset(sum, 0, sizeof(sum)); 73 memset(addv, 0, sizeof(addv)); 74 double ans = 0; 75 for(int i = 1; i<=2*n-1; i++) 76 { 77 int l = upper_bound(X+1, X+1+m, Line[i].le) - (X+1); 78 int r = upper_bound(X+1, X+1+m, Line[i].ri) - (X+1); 79 add(1, 1, m, l, r-1, Line[i].id); 80 ans += sum[1]*(Line[i+1].h-Line[i].h); 81 } 82 printf("Test case #%d\n", ++kase); 83 printf("Total explored area: %.2f\n\n", ans); 84 } 85 }
HDU1542 Atlantis —— 求矩形面积并 线段树 + 扫描线 + 离散化
原文：http://www.cnblogs.com/DOLFAMINGO/p/7746232.html
