Hdu 1542
线段树离散化以后进行扫描线求面积并。
具体就是用一条平行于$y$轴的直线自左向右地扫过去，然后每次扫到一个整块长方形记录面积。
记录方法是，一个矩形分成左右两个边，左边在线段树中增加，右边在线段树中减少。则当前线段树中的所有大于0的数的个数即为当前长方形的一边。另一边为当前边横坐标减去前一条边的横坐标。
需要离散化。
这里维护的线段树很特殊，只需要查询根节点的和，则在线段树直接维护离散前的数据长度，记录一下区间覆盖次数，大于0则有值，否则没有。注意线段树里面每个点维护的是第几段的覆盖次数。
http://www.cnblogs.com/scau20110726/archive/2013/03/21/2972808.html
2018/12/25 重写
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<set>
#include<queue>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
int kse = 0;
namespace flyinthesky {
const int MAXN = 500 + 5;
struct data {
int ymin, ymax, v;
db x, fymin, fymax;
bool operator < (const data &rhs) const {return x < rhs.x;}
} cz[1000];
int n, cnt, czcnt, minpos;
db whw[1000], ans;
#define lc (o << 1)
#define rc (o << 1 | 1)
#define M ((l + r) >> 1)
db sumv[MAXN * 4];
int lazy[MAXN * 4];
void pushup(int o, int l, int r) {
if (lazy[o]) {
sumv[o] = whw[r + 1] - whw[l];
} else sumv[o] = sumv[lc] + sumv[rc];
}
void update(int o, int l, int r, int x, int y, int v) {
if (x <= l && r <= y) {
lazy[o] += v;
if (lazy[o] > 0) sumv[o] = whw[r + 1] - whw[l]; else sumv[o] = sumv[lc] + sumv[rc];
return ;
}
if (x <= M) update(lc, l, M, x, y, v);
if (M < y) update(rc, M + 1, r, x, y, v);
pushup(o, l, r);
}
void clean() {
ms(sumv, 0), ms(lazy, 0), ans = 0.0, czcnt = cnt = 0;
}
int solve() {
clean();
for (int i = 1; i <= n; ++i) {
db x1, y1, x2, y2;
scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
cz[++czcnt] = (data){0, 0, 1, x1, y1, y2};
cz[++czcnt] = (data){0, 0, -1, x2, y1, y2};
whw[++cnt] = y1, whw[++cnt] = y2;
}
sort(whw + 1, whw + 1 + cnt), cnt = unique(whw + 1, whw + 1 + cnt) - whw - 1;
for (int i = 1; i <= czcnt; ++i) cz[i].ymin = lower_bound(whw + 1, whw + 1 + cnt, cz[i].fymin) - whw - 1, cz[i].ymax = lower_bound(whw + 1, whw + 1 + cnt, cz[i].fymax) - whw - 1;
// for (int i = 1; i <= czcnt; ++i) printf("cz %d: x=%.2lf, ymin=%.2lf, ymax=%.2lf, opt=%d\n", i, cz[i].x, cz[i].fymin, cz[i].fymax, cz[i].v);
// for (int i = 1; i <= czcnt; ++i) printf("cz %d: x=%.2lf, ymin=%d, ymax=%d, opt=%d\n", i, cz[i].x, cz[i].ymin, cz[i].ymax, cz[i].v);
sort(cz + 1, cz + 1 + czcnt);
cz[0] = (data){-1, -1, 0, 0, 0, 0};
for (int i = 1; i <= czcnt; ++i) {
ans += sumv[1] * (cz[i].x - cz[i - 1].x);
if (cz[i].ymin + 1 <= cz[i].ymax) update(1, 1, cnt, cz[i].ymin + 1, cz[i].ymax, cz[i].v);
}
printf("Test case #%d\nTotal explored area: %.2f\n\n", ++kse, ans);
return 0;
}
}
int main() {
while (scanf("%d", &flyinthesky::n) == 1 && flyinthesky::n) flyinthesky::solve();
return 0;
}
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#define ms(i,j) memset(i,j, sizeof i);
using namespace std;
const int MAXN = 100 + 5;
struct xian
{
int f; //up or down, up is -1, down is 1
double l, r;//the interval's end points
double h;//height
bool operator < (const xian &b) const
{
return h<b.h;
}
}a[MAXN*2];
double hashs[MAXN*2];//the hashsed points
int n;
#define lc o*2
#define rc o*2+1
#define M (l+r)/2
struct st
{
int col[MAXN*4*4];//col[i]>0 means this inerval was full marked
double sum[MAXN*4*4];//available room
void pushup(int o, int l, int r)
{
if (col[o]>0)
{
sum[o] = hashs[r+1]-hashs[l];
} else if (l==r) sum[o] = 0;
else {
sum[o] = sum[lc] + sum[rc];
}
}
void update(int o, int l ,int r, int x, int y, int c)
{
if (x<=l&&r<=y)
{
col[o] += c;
pushup(o,l,r);
return ;
}
if (x<=M) update(lc,l,M,x,y,c);
if (M<y) update(rc,M+1,r,x,y,c);
pushup(o,l,r);
}
}tree;
//binary-search the elements in hashs[]
int find(int x, int y, double v)
{
int l = x, r = y, mid;
while (l<r)
{
mid = (l+r)/2;
if (v>hashs[mid])
{
l = mid+1;
} else r = mid;
}
return r;
}
int main()
{
int kase = 0;
while (scanf("%d", &n)==1&&n)
{
kase++;
for (int i=0;i<n;i++)
{
double x1, y1, x2, y2;
scanf("%lf%lf%lf%lf", &x1,&y1,&x2,&y2);
a[i*2].f = 1; a[i*2+1].f = -1;
a[i*2].l = x1; a[i*2+1].l = x1;
a[i*2].r = x2; a[i*2+1].r = x2;
a[i*2].h = y1; a[i*2+1].h = y2;//add xian
hashs[i*2] = x1; hashs[i*2+1] = x2;//add hashs
}
sort(hashs, hashs+2*n); sort(a, a+2*n); //sort to hashs
//delete the repeated elements
int m = 1;
for (int i=1;i<2*n;i++)
if (hashs[i]!=hashs[i-1]) hashs[m++] = hashs[i];
//produce
ms(tree.col, 0);
double ans = 0;
for (int i=0;i<n*2;i++)
{
int l = find(0, m, a[i].l);
int r = find(0, m, a[i].r)-1;
/*int l = lower_bound(hashs, hashs+m, a[i].l)-hashs;
int r = lower_bound(hashs, hashs+m, a[i].r)-hashs-1;*/
if (r>=l) tree.update(1,0,m-2,l,r,a[i].f);//一定要r>=l,这里原来错了
ans += (a[i+1].h-a[i].h)*tree.sum[1];
}
printf("Test case #%d\nTotal explored area: %.2f\n\n", kase, ans);
}
return 0;
}
