poj 1151-atlantis-线段树扫描线求面积并
= =||好像放在草稿箱里长毛了~~~~~本来想写个好详细好详细的扫描线哒~~~可是看到代码都不想动了，再跟别的大牛的代码一比较，觉得自己这单点更新简直就是纯暴力伪线段树吖~~~还有那离散化【离散了还用函数去O（n）地找是怎么回事啊喂！】如果题目范围是10000个点估计我就布吉岛爆到哪里去了。。。。。所以还是不要教坏小孩子了~~看到这篇日志的童鞋默默转台就好。。。。其实100个点乖乖按线段存然后暴力就好~~~~吐槽完毕~~以上！
AC代码:
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 #include <vector> 5 using namespace std; 6 #define maxn 300 7 #define lson l, m, rt<<1 8 #define rson m+1, r, rt<<1|1 9 struct st 10 { 11 int cover; 12 double len; 13 }; 14 vector<st> sgt; 15 int n; 16 struct Line 17 { 18 double x, y_up, y_down; 19 int sign; 20 bool operator < (const Line that) const { 21 return x < that.x; 22 } 23 }; 24 vector<Line> line; 25 vector<double> Y; 26 void input() 27 { 28 line.clear(); 29 Y.clear(); 30 sgt.clear(); 31 sgt.resize(maxn<<1); 32 double x, y, a, b; 33 Line read; 34 scanf("%lf%lf%lf%lf", &x, &y, &a, &b); 35 read.x = x; read.sign = 1; read.y_down = y; read.y_up = b; 36 line.push_back(read); Y.push_back(y); 37 read.x = a; read.sign = -1; 38 line.push_back(read); Y.push_back(b); 39 for(int i = 1; i < n; i++) { 40 scanf("%lf%lf%lf%lf", &x, &y, &a, &b); 41 read.x = x; read.sign = 1; read.y_down = y; read.y_up = b; 42 line.push_back(read); 43 read.x = a; read.sign = -1; 44 line.push_back(read); 45 bool flag1 = 0, flag2 = 0; int l = Y.size(); 46 for(int j = 0; j < l; j++) { 47 if(Y[j] == y) flag1 = 0; 48 if(Y[j] == b) flag2 = 0; 49 } 50 if(!flag1) Y.push_back(y); 51 if(!flag2) Y.push_back(b); 52 } 53 sort(line.begin(), line.end()); 54 sort(Y.begin(), Y.end()); 55 } 56 57 void build(int l, int r, int rt) 58 { 59 sgt[rt].cover = 0; 60 sgt[rt].len = 0; 61 if(l == r) { 62 sgt[rt].len = Y[l] - Y[l-1]; 63 return; 64 } 65 int m = (l + r)>>1; 66 build(lson); 67 build(rson); 68 } 69 void insert(int l, int r, int rt, int L, int R, int sign) 70 { 71 if(l == r) { 72 sgt[rt].cover += sign; 73 return; 74 } 75 sgt[rt].len = 0; 76 int m = (l+r)>>1; 77 if(L <= m) insert(lson, L, R, sign); 78 if(m < R) insert(rson, L, R, sign); 79 } 80 double getSum(int l, int r, int rt) 81 { 82 if(l == r) { 83 if(sgt[rt].cover > 0) return sgt[rt].len; 84 return 0; 85 } 86 int m = (l + r)>>1; 87 double a, b, ans; 88 ans = getSum(lson); 89 ans += getSum(rson); 90 return ans; 91 } 92 struct node 93 { 94 int st, nd; 95 }; 96 node getNum(double y1, double y2) 97 { 98 int l = Y.size(); 99 node res; 100 for(int i = 0; i < l; i++) { 101 if(Y[i] == y1) res.st = i+1; 102 if(Y[i] == y2) res.nd = i; 103 } 104 return res; 105 } 106 void work(int cas) 107 { 108 input(); 109 int N = Y.size(); 110 build(1, N-1, 1); 111 int l = line.size(); 112 double ans = 0; 113 for(int i = 0; i < l; i++) { 114 node rec = getNum(line[i].y_down, line[i].y_up); 115 if(i == 0) insert(1, N-1, 1, rec.st, rec.nd, line[i].sign ); 116 if(i == 0) continue; 117 double length = line[i].x - line[i-1].x; 118 ans += length*getSum(1, N-1, 1); 119 insert(1, N-1, 1, rec.st, rec.nd, line[i].sign ); 120 } 121 printf("Test case #%d Total explored area: %0.2f ", cas, ans); 122 } 123 int main() 124 { 125 int cnt = 0; 126 while(1) { 127 scanf("%d", &n); if(n == 0) break; 128 work(++cnt); 129 } 130 return 0; 131 }