【poj1151】矩形面积并，扫描线+离散化+线段树

原题：http://poj.org/problem?id=1151

题意：给出若干组矩形左上角和右下角的坐标（坐标可能为小数），求出所有矩形所覆盖的面积，重叠部分只算一次。

扫描线示意图.jpg

思路：如图所示，假想一条扫描线从下向上移动，每次遇到矩形上底或者下底便计算一次扫过的矩形面积，并加到总和中去。如图所示，依次求出不同颜色矩形的面积，想加便可求得所有矩形覆盖的总面积。

扫描线的移动由程序来实现实质上是在各个矩形的底边按纵坐标从小到大跳动，每跳动一次需要计算一次扫过的矩形面积。面积=跳动的长度*该段x方向被矩形覆盖的长度，暂且将其设成S=Y*X。

首先，我们需要将矩形的底边的纵坐标按从小到大进行排序，Y即为相邻两个底边的差值，同时，我们还需要记录底边的横坐标范围，以便每扫过一条底边后更新X（当扫面线经过一条底边时，意味着有一个矩形进入或者退出扫描区域）。于是，我们定义以下结构体：

struct line{
    double lf,rf,y;                  //某底边的左右端点坐标，纵坐标
    int d;                           //区分上底和下底的标记，为方便更新X，下底设为1，上底设为-1
}scan[MAXN];

如何高效地更新X呢，考虑到X实质上是扫描线上矩形所覆盖的总长度，遇到底边是相当于修改扫描线上某一区间被覆盖的情况。类似于区间修改与求和问题，由此联想到线段树，因此可以使用线段树来维护扫描线上被矩形覆盖的情况。但是横坐标为浮点数，因此首先要将所有的横坐标进行排序离散化处理，即将所有的矩形的边横坐标从小到大排序，将排序序号作为线段树的区间号。同时，我们还要保存原来真实的浮点值，以便计算长度。
因此树节点可以如下定义：

struct node{
    int l,r;//左右整点区间
    int c;//覆盖标记
    double cnt;//覆盖长度
    double lf,rf;//左右实数区间 
}tree[MAXN*4];

覆盖标记用来表示该节点所代表的区间被一个完整的矩形完全覆盖（注意是被一个矩形完全覆盖，而非由多个矩形完全覆盖），覆盖长度表示该节点所代表的区间被所有矩形所覆盖的长度。

//ac代码
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<cmath>
#include<queue>
#include<string>
#include<cstring>
#include<algorithm> 
using namespace std;
#define MAXN 201

struct node{
    int l,r;//左右整点区间
    int c;//覆盖标记
    double cnt;//覆盖长度
    double lf,rf;//左右实数区间 
}tree[MAXN*4];

struct line{
    double lf,y,rf;
    int d;
}scan[MAXN];

double x[MAXN];

bool cmp(line l1,line l2){
    return l1.y<l2.y;
}

void build(int i,int s,int e){
    tree[i].l=s;
    tree[i].r=e;
    tree[i].lf=x[s];
    tree[i].rf=x[e];
    tree[i].c=tree[i].cnt=0;
    if (s+1==e) return;
    int mid = (s+e)>>1;
    build(i<<1,s,mid);
    build(i<<1|1,mid,e);
}

void calen(int i){
    if (tree[i].c>0){
        tree[i].cnt=tree[i].rf-tree[i].lf;  //cout<<i<<" "<<tree[i].lf<<" "<<tree[i].rf<<" "<<tree[i].cnt<<"#"<<endl;
        return;
    }
    if (tree[i].r-tree[i].l==1) tree[i].cnt=0;
    else tree[i].cnt=tree[i<<1].cnt+tree[i<<1|1].cnt;
}

void updata(int i,line l){
    if (tree[i].lf>=l.lf&&tree[i].rf<=l.rf){
        tree[i].c+=l.d;
        calen(i);
        return;
    }
    if (tree[i].lf>=l.rf||tree[i].rf<=l.lf) return;
    updata(i<<1,l);
    updata(i<<1|1,l);
    calen(i);
}

int main()
{
    int n,i,j,icase=0;
    double x1,y1,x2,y2;
    while(~scanf("%d",&n)){
        if (n==0) break;
        icase++;
        for (i=0;i<n;++i){
            scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
            scan[2*i].lf=x1;
            scan[2*i].rf=x2;
            scan[2*i].y=y1;
            scan[2*i].d=1;
            scan[2*i+1].lf=x1;
            scan[2*i+1].rf=x2;
            scan[2*i+1].y=y2;
            scan[2*i+1].d=-1;
            x[2*i]=x1;
            x[2*i+1]=x2;
        }
        sort(x,x+2*n);
        sort(scan,scan+2*n,cmp);
        //for (i=0;i<2*n;++i) cout<<x[i]<<" "<<scan[i].y<<" ";
        //cout<<endl;
        build(1,0,2*n-1);
        updata(1,scan[0]);
        double res=0;
        //cout<<scan[0].lf<<" "<<scan[0].rf<<endl; 
        //for (i=1;i<=7;++i) cout<<tree[i].c<<" "<<tree[i].cnt<<" "<<tree[i].lf<<" "<<tree[i].rf<<endl;
        //cout<<"$"<<endl;
        for (i=1;i<2*n;++i){
            res+=(scan[i].y-scan[i-1].y)*tree[1].cnt;
            updata(1,scan[i]);
            //cout<<scan[i].lf<<" "<<scan[i].rf<<endl;
            //for (int k=1;k<=7;++k) cout<<tree[k].c<<" "<<tree[k].cnt<<endl;
            //cout<<"$"<<endl;
        }
        printf("Test case #%d\nTotal explored area: %.2f\n\n",icase,res);
    }
}