题目链接：http://poj.org/problem?id=1151
题目大意：坐标轴上给你n个矩形， 问这n个矩形覆盖的面积
题目思路：矩形面积并。
代码如下：
#include<stdio.h> #include<vector> #include<algorithm> using namespace std; const int N = 107; struct Line { int l, r, flag; double h; Line(){} Line(int l, int r, int flag, double h):l(l), r(r), flag(flag), h(h) {} bool operator<(Line &b) const { return h<b.h; } }; int n; vector<double> vec; vector<Line>line; struct node { int l, r, flag; double len; }; node tree[N << 4]; void build(int l, int r, int k) { tree[k].l = l, tree[k].r = r, tree[k].len = 0, tree[k].flag = 0; if(l == r - 1) return; int mid = (l + r) >> 1; build(l, mid, k<<1); build(mid, r, k<<1|1); } void updata_up(int k) { if(tree[k].flag) tree[k].len = vec[tree[k].r-1] - vec[tree[k].l-1]; else if (tree[k].l == tree[k].r - 1) tree[k].len = 0; else tree[k].len = tree[k<<1].len + tree[k<<1|1].len; } void updata(int l, int r, int k, int x) { if(tree[k].l >= l && tree[k].r <= r) { tree[k].flag += x; updata_up(k); return; } if(tree[k<<1].r > l) updata(l, r, k<<1, x); if(tree[k<<1|1].l < r) updata(l, r, k<<1|1, x); updata_up(k); } int main() { int cases = 0; while(scanf("%d", &n),n) { vec.clear(); line.clear(); double x1[105], y1[105], x2[105], y2[105]; for(int i=0; i<n; ++ i) { scanf("%lf%lf%lf%lf", &x1[i], &y1[i], &x2[i], &y2[i]); vec.push_back(x1[i]); vec.push_back(x2[i]); } sort(vec.begin(), vec.end()); vec.erase(unique(vec.begin(), vec.end()), vec.end()); for(int i=0; i<n; ++ i) { int x = lower_bound(vec.begin(), vec.end(), x1[i]) - vec.begin() + 1; int y = lower_bound(vec.begin(), vec.end(), x2[i]) - vec.begin() + 1; line.push_back(Line(x, y, 1, y1[i])); line.push_back(Line(x, y, -1, y2[i])); } sort(line.begin(), line.end()); build(1, vec.size() + 1, 1); double ans = 0; for(int i=0; i<line.size(); ++ i) { if(i != 0) ans += (line[i].h - line[i-1].h)*tree[1].len; updata(line[i].l, line[i].r, 1, line[i].flag); } printf("Test case #%d Total explored area: %.2f ", ++ cases, ans); } }