POJ 1542 Atlantis （线段树+扫描线+离散化）

太过爱你忘了你带给我的痛 2022-06-12 03:47 193阅读 0赞

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 file 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

题解：

第一次做扫描线的题就做了一天。。。终于算是理解了，要做出这题不仅要会扫描线，还要会离散化

先说离散化，所谓离散化，就是如果数据范围很大，而数据的值对某些操作没有影响，只有他们的大小关系对操作有影响，这时我们就可以离散化操作，比如这题横坐标的范围很大，但是给的矩形的个数却很少，如果开一个很大的数组肯定是要爆的，而且一个矩形还浪费好多区间，这时我们就如映射一般，列如：一个矩形两端x1=1 x2=100,但是他们中间没有别的矩形的坐标了，这时我们就把x=1映射为0，而x=100映射为1来判断有没有被覆盖。。这就是我理解的离散化

如果还不懂看博客http://www.cnblogs.com/forgot93/archive/2014/07/02/3819956.html

理解了离散化了以后再读下去，本题是扫描线的基础题，思想就是把矩形的纵坐标组成的线看成扫描线，从下往上扫，然后依次按照是上边还是下边为区间赋值，是上边就把该线段的横坐标所对应离散化的区间加上-1，是下边就加上1。。说的不太明白要上图，这个博客图解释的比较到位http://blog.csdn.net/u013480600/article/details/22548393

至于比较易懂的代码，看http://m.blog.csdn.net/tomorrowtodie/article/details/52048323

我的代码里面有详细的解释

ps:

我在写了这篇博客知道的离散化知识或许可以帮助更好的理解这题

这题数据范围很大,直接搞超时\+超内存,需要离散化:

离散化简单的来说就是只取我们需要的值来用,比如说区间\[1000,2000\],\[1990,2012\] 我们用不到\[-∞,999\]\[1001,1989\]\[1991,1999\]\[2001,2011\]\[2013,+∞\]这些值,所以我只需要1000,1990,2000,2012就够了,将其分别映射到0,1,2,3,在于复杂度就大大的降下来了

所以离散化要保存所有需要用到的值,排序后,分别映射到1~n,这样复杂度就会小很多很多

而这题的难点在于每个数字其实表示的是一个单位长度(并且一个点),这样普通的离散化会造成许多错误(包括我以前的代码,poj这题数据奇弱)

给出下面两个简单的例子应该能体现普通离散化的缺陷:

1-10 1-4 5-10

1-10 1-4 6-10

为了解决这种缺陷,我们可以在排序后的数组上加些处理,比如说\[1,2,6,10\]

如果相邻数字间距大于1的话,在其中加上任意一个数字,比如加成\[1,2,3,6,7,10\],然后再做线段树就好了.

我的代码：

#include<algorithm>
    #include<iostream>
    #include<cstring>
    #include<stdio.h>
    #include<math.h>
    #include<string>
    #include<stdio.h>
    #include<queue>
    #include<stack>
    #include<map>
    #include<deque>
    using namespace std;
    const int N=111;//离散化了以后区间就那么小那么任性
    struct edge
    {
        double l,r;//l,r代表线段的左右端点
        double h;//代表线段高度，即纵坐标
        int d;//如果值1则为下边，-1为上边
    };
    int cmp(edge x,edge y)//根据高来从小到大排序
    {
        return x.h<y.h;
    }
    edge a[N*2];//存边
    struct node
    {
        int l,r;
        int s;//存区间是否被完全覆盖
        double len;//存区间被覆盖的长度
    };
    node t[N*8];//N*8的大小是因为对应N*2个端点，然后线段树开四倍乘起来就是8倍
    double x[N*2];//存每一个边的两个横坐标，用于离散化操作，
    void Build(int l,int r,int num)//日常建树
    {
        t[num].l=l;
        t[num].r=r;
        t[num].s=0;
        t[num].len=0;
        if(l==r)
            return;
        int mid=(l+r)/2;
        Build(l,mid,num*2);
        Build(mid+1,r,num*2+1);
    }
    void Pushup(int num)//区间合并，向上更新
    {
        if(t[num].s)//如果区间完全被覆盖
        {
            t[num].len=x[t[num].r+1]-x[t[num].l];//长度等于全长，至于为什么是t[num].r+1,这和离散化有关，+1才能获得端点坐标
        }
        else if(t[num].l==t[num].r)//这是一个点
        {
            t[num].len=0;
        }
        else//不完全覆盖的情况
        {
            t[num].len=t[num*2].len+t[num*2+1].len;
        }
    }
    void Update(int l,int r,int num,int d)//日常更新
    {
        if(l==t[num].l&&r==t[num].r)
        {
            t[num].s+=d;
            Pushup(num);
            return;
        }
        int mid=(t[num].l+t[num].r)/2;
        if(r<=mid)
            Update(l,r,num*2,d);
        else if(l>mid)
            Update(l,r,num*2+1,d);
        else
        {
            Update(l,mid,num*2,d);
            Update(mid+1,r,num*2+1,d);
        }
        Pushup(num);
    }
    int main()
    {
        int i,j,k,ans=1,n,tot;
        double s,x1,x2,y1,y2;
        while(scanf("%d",&n)!=EOF&&n)
        {
            tot=0;
            for(i=0;i<n;i++)
            {
                scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
                a[tot].l=x1;//保存边的情况
                a[tot+1].l=x1;
                a[tot].r=x2;
                a[tot+1].r=x2;
                a[tot].h=y1;
                a[tot+1].h=y2;
                a[tot].d=1;
                a[tot+1].d=-1;
                x[tot]=x1;//保存两个横坐标
                x[tot+1]=x2;
                tot+=2;
            }
            sort(a,a+tot,cmp);
            sort(x,x+tot);//排序为了离散化去重
            k=1;
            for(i=1;i<tot;i++)//去重
            {
                if(x[i]!=x[i-1])
                {
                    x[k]=x[i];
                    k++;
                }
            }
            Build(0,k-1,1);//去重后离散化的长度为k-1
            s=0;
            for(i=0;i<tot;i++)
            {
                int l=lower_bound(x,x+k,a[i].l)-x;//在各个横坐标中寻找该边对应的横坐标对应的标号
                int r=lower_bound(x,x+k,a[i].r)-x-1;//这里-1了,理解离散化以后应该能懂,离散化后每一个节点代表着一根线且后面的端点为开区间
                Update(l,r,1,a[i].d);//更新区间信息
                s+=t[1].len*(a[i+1].h-a[i].h);//面积等于区间覆盖的总长乘上两个扫描线的高度差
            }
             printf("Test case #%d\n",ans);
             ans++;
             printf("Total explored area: %.2f\n\n",s);
        }
    
    }