poj1151 Atlantis(线段树+扫描线)

Description
There are several ancient Greek texts that contain descriptions of the fabled island Atlantis. Some of these texts even include maps of parts of the island. But unfortunately, these maps describe different regions of Atlantis. Your friend Bill has to know the total area for which maps exist. You (unwisely) volunteered to write a program that calculates this quantity.

Input
The input consists of several test cases. Each test case starts with a line containing a single integer n (1 <= n <= 100) of available maps. The n following lines describe one map each. Each of these lines contains four numbers x1;y1;x2;y2 (0 <= x1 < x2 <= 100000;0 <= y1 < y2 <= 100000), not necessarily integers. The values (x1; y1) and (x2;y2) are the coordinates of the top-left resp. bottom-right corner of the mapped area.
The input file is terminated by a line containing a single 0. Don’t process it.

Output
For each test case, your program should output one section. The first line of each section must be “Test case #k”, where k is the number of the test case (starting with 1). The second one must be “Total explored area: a”, where a is the total explored area (i.e. the area of the union of all rectangles in this test case), printed exact to two digits to the right of the decimal point.
Output a blank line after each test case.
Sample Input

2
10 10 20 20
15 15 25 25.5
0

Sample Output
Test case #1
Total explored area: 180.00

分析：
扫描线，好像是个挺重要的东西
今天就学习一下吧
网上也没有很直观的，就自己说一下吧

我们先将x轴上的数离散化
在y方向上建立一棵线段树
想像有一扫描仪从左向右扫描
线段树的作用就是记录当前的y轴上的覆盖线段长度

每次扫描就从当前xi跳到xi+1，记录xi到xi+1的长度
乘上当前线段树中的覆盖长度，就是扫过的面积了
红线代表加入，蓝线代表退出

主程序中

初始把每个矩形拆成两条线段
进行x和y坐标的分别排序

build

线段树节点中的l和r记录的是离散后的y值
ml，mr记录的是实际y值
s是该区间的覆盖次数
len是该节点所管辖的区间覆盖线段长度
这里需要注意一下
在构建左右儿子的时候
递归调用的是(l,mid),(mid,r)

update（维护len）

update的时候，如果s>0
那就是完全覆盖
如果是叶子节点，那么len=0
否则len=lc.len+rc.len

add

在add的时候,如果完全覆盖了该区间，就直接打个标记
分别递归到左右儿子里去
如果当前区间没有完全覆盖线段树节点，而且又涉及左右儿子
那么就把当前区间劈成两段，进行递归

tip

所有和坐标有关的数组都是double类型的

这里写代码片
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;

const double eps=1e-8; 

const int N=301;
struct node{
    double x,ya,yb;
    int ff;
};
node li[N];
int n,tot;
double yi[N];
struct nd{
    int l,r,s;
    double ml,mr,len;
};
nd t[N*3];

int cmp(const node &a,const node &b)
{
    return a.x-b.x<eps;
}

void build(int bh,int l,int r)
{
    t[bh].l=l;t[bh].r=r;
    t[bh].ml=yi[l];
    t[bh].mr=yi[r];
    t[bh].s=0;
    t[bh].len=0;
    if (t[bh].l+1==t[bh].r) return;
    int mid=(l+r)>>1;
    build(bh<<1,l,mid);
    build(bh<<1|1,mid,r); 
}

void update(int bh)
{
    if (t[bh].s>0){
        t[bh].len=t[bh].mr-t[bh].ml;
    }
    else if (t[bh].r-t[bh].l==1){
        t[bh].len=0;
    }
    else {
        t[bh].len=t[bh<<1].len+t[bh<<1|1].len;
    }
    return;
}

void add(int bh,node b)
{
    if (t[bh].ml==b.ya&&t[bh].mr==b.yb)
    {
        t[bh].s+=b.ff;
        update(bh);
        return;
    }   
    if (b.yb<=t[bh<<1].mr) add(bh<<1,b);
    else if (b.ya>=t[bh<<1|1].ml) add(bh<<1|1,b);
    else
    {
        node temp=b;
        temp.yb=t[bh<<1].mr;
        add(bh<<1,temp);
        temp=b;
        temp.ya=t[bh<<1|1].ml;
        add(bh<<1|1,temp);
    }
    update(bh);
}

int main()
{
    int T=1;
    scanf("%d",&n);
    while (n)
    {
        tot=0;
        double x,y,xx,yy;
        for (int i=1;i<=n;i++)
        {
            scanf("%lf%lf%lf%lf",&x,&y,&xx,&yy);
            tot++; yi[tot]=y;       
            li[tot].x=x;li[tot].ya=y;li[tot].yb=yy;li[tot].ff=1;
            tot++; yi[tot]=yy;
            li[tot].x=xx;li[tot].ya=y;li[tot].yb=yy;li[tot].ff=-1;
        }
        sort(li+1,li+1+tot,cmp);   //按x排序 
        sort(yi+1,yi+1+tot);   //把y也离散一下 
        build(1,1,tot);
        add(1,li[1]);
        double sum=0;
        for (int i=2;i<=tot;i++)
        {
            sum+=t[1].len*(li[i].x-li[i-1].x);
            add(1,li[i]);
        }
        printf("Test case #%d\n",T++);
        printf("Total explored area: %0.2lf\n\n",sum);
        scanf("%d",&n);
    }
    return 0;
}