（POJ 1151，HDU 1542，ZOJ 1128） Atlantis

素颜马尾好姑娘i 2022-06-17 04:11 180阅读 0赞

## 题目： ##

> Time Limit: 2 Seconds Memory Limit: 65536 KB  
> 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 it1.  
> 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

## 题意： ##

> 求矩形的面积并

## 题解: ##

> 扫描线+线段树+离散化  
> ![Atlantis][]  
> 把每个矩形投影到y坐标轴上来，然后我们可以枚举矩  
> 形的 x 坐标，然后检测当前相邻x坐标上y方向的合法长度，两种相乘就是面积。  
> 然后通过“扫描线”的方法来进行扫描，枚举 x 的竖边，矩形的左边那条竖  
> 边就是入边，右边那条就是出边了。然后把所有这些竖边按照 x 坐标递增排序，每  
> 次进行插入操作，由于坐标不一定为整数，因此需要进行离散化处理。每次插入时  
> 如果当前区间被完全覆盖，那么就要对 cov 域进行更新。入边 +1 出边 -1，更新完  
> 毕后判断当前节点的 cov 域是否大于 0 ，如果大于 0，那么当前节点的 len 域就是  
> 节点所覆盖的区间。否则，如果是叶子节点，则 len=0。 如果内部节点，则 len=左  
> 右儿子的 len 之和

## 代码: ##

#include <iostream>
    #include <cstring>
    #include <cstdio>
    #include <algorithm>
    #include <iomanip>
    using namespace std;
    
    const int maxn = 1000;
    double y[maxn];
    int n;
    struct Line
    {
        //把一段段平行于y轴的线段表示成数组 ，
        //x是线段的x坐标，y1,y2线段对应的下端点和上端点的坐标
        //一个矩形 ，左边的那条边f为1，右边的为-1，
        double x,y1,y2;
        int flag;
        bool operator < (const Line &line)
        {
            return x < line.x;
        }
    }line[maxn];
    
    struct node
    {
        int left;//线段树的左右整点
        int right;
        int cov;//c用来记录重叠情况
        double len,lf,rf;//len用来计算实在的长度，rf,lf分别是对应的左右真实的浮点数端点
    }node[maxn];
    
    void length(int t)//计算长度
    {
        if(node[t].cov > 0)
        {
            node[t].len = node[t].rf-node[t].lf;
            return;
        }
        if(node[t].left+1 == node[t].right)
            node[t].len = 0;
        else
            node[t].len = node[t<<1].len + node[t<<1|1].len;
    
    }
    void build(int t,int l,int r)
    {
        node[t].left = l;
        node[t].right = r;
        node[t].len = node[t].cov = 0;
        node[t].lf = y[l];
        node[t].rf = y[r];
        if(l+1==r)
            return;
        int mid = (l+r)>>1;
        build(t<<1,l,mid);
        build(t<<1|1,mid,r);
    }
    
    void update(int t,Line e)//加入线段e，后更新线段树
    {
        if(e.y1 == node[t].lf&&e.y2 == node[t].rf)
        {
            node[t].cov += e.flag;
            length(t);
            return;
        }
        if(e.y2<=node[t<<1].rf)
            update(t<<1,e);
        else if(e.y1>=node[t<<1|1].lf)
            update(t<<1|1,e);
        else
        {
            Line tmp = e;
            tmp.y2 = node[t<<1].rf;
            update(t<<1,tmp);
            tmp = e;
            tmp.y1 = node[t<<1|1].lf;
            update(t<<1|1,tmp);
        }
        length(t);
    }
    
    int main()
    {
        int Case = 0,t;
        double x1,y1,x2,y2;
        while(cin>>n&&n)
        {
            cout<<"Test case #"<<++Case<<endl;
            t = 1;
            for(int i=1;i<=n;i++)
            {
                cin>>x1>>y1>>x2>>y2;
                line[t].x = x1;
                line[t].y1 = y1;
                line[t].y2 = y2;
                line[t].flag = 1;
                y[t] = y1;
                t++;
                line[t].x = x2;
                line[t].y1 = y1;
                line[t].y2 = y2;
                line[t].flag = -1;
                y[t] = y2;
                t++;
            }
            sort(line+1,line+t);
            sort(y+1,y+t);
            build(1,1,t-1);
            update(1,line[1]);
            double ans = 0;
            for(int i=2;i<t;i++)
            {
                ans += node[1].len*(line[i].x - line[i-1].x);
                update(1,line[i]);
            }
            printf("Total explored area: %.2f\n\n",ans);
        }
        return 0;
    }

[Atlantis]: /images/20220617/654dffa8feda40638d29d4b5484ad3c1.png