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