学步园

题意：给定n（n <=100）个矩形的左下角和右上角的坐标（0<=x y<=100000），求覆盖的面积。
题解：把所有的从坐标离散化，横向将所有垂直的线段排序并标记是矩形的左边还是右边线段，扫描时线段树维护有效的长度，累加得到答案。

Sure原创，转载请注明出处。

#include <iostream>
#include <cstdio>
#include <memory.h>
#include <algorithm>
using namespace std;
const int maxn = 102;
struct line
{
    double x,down,up;
    int left;
    bool operator < (const line &other) const
    {
        return x < other.x;
    }
}vertical_line[maxn << 1];
struct node
{
    int l,r;
    int lazy;
    double len;
}seg[maxn << 3];
double yy[maxn << 1];
int n,top,cas = 0;

void read()
{
    double x1,x2,y1,y2;
    for(int i=0;i<n;i++)
    {
        scanf("%lf %lf %lf %lf",&x1,&y1,&x2,&y2);
        vertical_line[i].x = x1;
        vertical_line[i].down = y1;
        vertical_line[i].up = y2;
        vertical_line[i].left = 1;
        yy[i] = y1;

        vertical_line[i+n].x = x2;
        vertical_line[i+n].down = y1;
        vertical_line[i+n].up = y2;
        vertical_line[i+n].left = -1;
        yy[i+n] = y2;
    }
    sort(vertical_line ,vertical_line + 2 * n);
    sort(yy , yy + 2 * n);
    top = unique(yy , yy + 2 * n) - yy;
    return;
}

void biuld(int l,int r,int num)
{
    seg[num].l = l;
    seg[num].r = r;
    seg[num].lazy = 0;
    seg[num].len = 0.0;
    if(l + 1 == r) return;
    int mid = (l + r) >> 1;
    biuld(l , mid , num << 1);
    biuld(mid , r , num << 1 | 1);
    return;
}

void UP(int num)
{
    if(seg[num].lazy > 0)
    {
        seg[num].len = yy[seg[num].r] - yy[seg[num].l];
    }
    else if(seg[num].l + 1 == seg[num].r)
    {
        seg[num].len = 0.0;
    }
    else
    {
        seg[num].len = seg[num << 1].len + seg[num << 1 | 1].len;
    }
    return;
}

void DOWN(int num)
{
    if(seg[num].lazy > 0 && seg[num].l + 1 < seg[num].r)
    {
        seg[num << 1].lazy += seg[num].lazy;
        seg[num << 1 | 1].lazy += seg[num].lazy;
        seg[num].lazy = 0;
        seg[num << 1].len = yy[seg[num << 1].r] - yy[seg[num << 1].l];
        seg[num << 1 | 1].len = yy[seg[num << 1 | 1].r] - yy[seg[num << 1 | 1].l];
    }
    return;
}

void update(int l,int r,int num,int val)
{
    if(l == seg[num].l && r == seg[num].r && val + seg[num].lazy >= 0)
    {
        seg[num].lazy += val;
        UP(num);
        return;
    }
    DOWN(num);
    int mid = (seg[num].l + seg[num].r) >> 1;
    if(mid >= r) update(l , r , num << 1 , val);
    else if(l >= mid) update(l , r , num << 1 | 1 , val);
    else
    {
        update(l , mid , num << 1 , val);
        update(mid , r , num << 1 | 1 , val);
    }
    UP(num);
    return;
}

void addline(int i)
{
    int bjd = lower_bound(yy , yy + top , vertical_line[i].down) - yy;
    int bju = lower_bound(yy , yy + top , vertical_line[i].up) - yy;
    update(bjd , bju , 1 , vertical_line[i].left);
    return;
}

void solve()
{
    double ans = 0.0;
    addline(0);
    for(int i=1;i<2*n;i++)
    {
        ans += seg[1].len * (vertical_line[i].x - vertical_line[i-1].x);
        addline(i);
    }
    printf("Test case #%d\n",++cas);
    printf("Total explored area: %.2f\n\n",ans);
    return;
}

int main()
{
    while(~scanf("%d",&n) && n)
    {
        read();
        biuld(0,top-1,1);
        solve();
    }
    return 0;
}