POJ1151/hdu1542 Atlantis 题解【扫描线】【线段树】

点击量：245

    扫描线入门题。不过要注意多组数据。

目录

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 

Source

Mid-Central European Regional Contest 2000

题解：

    题目意思很简单，就是求矩形的面积并。

    矩形面积并可以用容斥来\(O(n^2)\)求，但是在不知道一块区域被覆盖了多少次时，这种方法会很麻烦。扫描线可以在离散化后用线段树做到\(O(n\log n)\)。

    对于很多个矩形，它们可能有相交的部分。如果我们想让一维的直线相交的部分只计算一次，比较好办，直接用差分就可以\(O(n)\)解决，只用统计不为0的个数就可以了。但是二维就不能直接这样做了，二维平面的矩形在两个维度上都有重合。

    我们试想把\(n\times m\)的二维其中一维分解成\(m\)段长为\(n\)的一维直线，是可以完成的，但是当\(n,m\)范围很大时，这种做法就不现实了。考虑到矩形面积并出来的图形的拐点总会与原矩形的顶点共线，我们可以按照原矩形的顶点来离散化。

    离散化后，矩形最多被分成\(2n\)个区间（此处的\(n\)是矩形个数），也就是我们认为某一个区间里，矩形的宽度是一定的，形状一定是规则的。我们就可以用线段树完成上面提到的一维差分的过程，每次统计被覆盖次数大于等于1的区间长度和。

    统计区间长度和是在改变区间出现次数的同时，更新区间长度和的。当线段树上的一个节点所代表的区间刚好被覆盖，那么这一段区间的长度就直接全部统计，如果把叶子节点也看作区间，它们是一样的。同时，如果一个节点的区间没有完全被覆盖，这个区间所被覆盖的长度就应该从它的子树更新。

    这样，我们把扫描线按横坐标排序，遇到一个矩形的左侧，就把这个矩形的宽区间+1；遇到右侧-1。对于每个宽度一定的区域，我们把这个宽度乘上这个区域的长度，就是这个区域对答案所做出的贡献。

    遇到红色的线，就把这条线所在的位置区间+1。假设我们统计到第5列，从上到下分别是0 2 2 1 1 0，这段横着的区间长为1，竖着的有3格被覆盖，那么这段面积就计算为4。

    所以离散化后用线段树来做，就可以完成这道题目了。(吐槽poj还在卡评测 在hdu上过了。

Code：

#include<cstdio>
#include<cstring>
#include<map>
#include<algorithm>
#define ls (k<<1)
#define rs (k<<1|1)
#define mid (l+r>>1)
#define Mid (t[k].l+t[k].r>>1)
using std::map;
struct line
{
    double up,down,x;
    int v;
    friend bool operator <(line a,line b)
    {
        return a.x<b.x;
    }
    line(double x,double up,double down,int v)
    {
        this->x=x;
        this->up=up;
        this->down=down;
        this->v=v;
    }
    line(){}
}b[205];
struct node
{
    int l,r;
    double v;
    int num;//v是指子树的真实值而不是离散值
    node(int l,int r)
    {
        this->l=l;
        this->r=r;
        v=0.0,num=0;
    }
    node(){}
}t[1000];
double a[205];//坐标
void build(int k,int l,int r)
{
    t[k]=node(l,r);
    if(l==r)
        return;
    build(ls,l,mid);
    build(rs,mid+1,r);
    return;
}
void change(int k,int l,int r,int x)
{
    if(t[k].l==l&&t[k].r==r)
    {
        t[k].num+=x;
        if(t[k].num)
            t[k].v=a[r+1]-a[l];
        else
            t[k].v=(t[k].l!=t[k].r)*(t[ls].v+t[rs].v);
        return;
    }
    if(r<=Mid)
        change(ls,l,r,x);
    else if(l>Mid)
        change(rs,l,r,x);
    else
    {
        change(ls,l,Mid,x);
        change(rs,Mid+1,r,x);
    }
    if(t[k].num)
        t[k].v=a[t[k].r+1]-a[t[k].l];
    else
        t[k].v=t[ls].v+t[rs].v;
    return;
}
map<double,int> m;
int main()
{
    int n,cnt=0;
    scanf("%d",&n);
    while(n)
    {
        ++cnt;
        build(1,1,n<<1);
        for(int i=1;i<=n;++i)
        {
            double lx,ly,rx,ry;
            scanf("%lf%lf%lf%lf",&lx,&ly,&rx,&ry);
            b[(i<<1)-1]=line(lx,ry,ly,1);//一个矩形在一个方向上产生两条扫描线
            b[i<<1]=line(rx,ry,ly,-1);
            a[(i<<1)-1]=ly;
            a[i<<1]=ry;
        }
        std::sort(a+1,a+1+2*n);
        for(int i=1;i<=2*n;++i)//离散化
            m[a[i]]=i;
        for(int i=1;i<=n;++i)
        {
            b[(i<<1)-1].up=m[b[(i<<1)-1].up];
            b[(i<<1)-1].down=m[b[(i<<1)-1].down];
            b[i<<1].up=m[b[i<<1].up];
            b[i<<1].down=m[b[i<<1].down];
        }
        std::sort(b+1,b+1+2*n);
        double ans=0;
        for(int i=1;i<2*n;++i)
        {
            change(1,b[i].down,b[i].up-1,b[i].v);
            ans+=t[1].v*(b[i+1].x-b[i].x);//纵区间覆盖长度×横区间长度
        }
        printf("Test case #%d\n",cnt);
        printf("Total explored area: %.2lf\n\n",ans);
        scanf("%d",&n);
    }
    return 0;
}