247. 亚特兰蒂斯

男娘i 2021-11-02 06:14 318阅读 0赞

[![知识共享许可协议][80x15.png]][80x15.png 1]  
本作品采用[知识共享署名-相同方式共享 4.0 国际许可协议][80x15.png 1]进行许可。  
先安利一篇博客扫描线  
题目链接；[https://www.acwing.com/problem/content/249/][https_www.acwing.com_problem_content_249]  
题目：有几个古希腊书籍中包含了对传说中的亚特兰蒂斯岛的描述。

其中一些甚至包括岛屿部分地图。

但不幸的是，这些地图描述了亚特兰蒂斯的不同区域。

您的朋友Bill必须知道地图的总面积。

你自告奋勇写了一个计算这个总面积的程序。  
输入格式

输入包含多组测试用例。

对于每组测试用例，第一行包含整数n，表示总的地图数量。

接下来n行，描绘了每张地图，每行包含四个数字x1,y1,x2,y2  
（不一定是整数）,(x1,y1)和(x2,y2)

分别是地图的左上角位置和右下角位置。

当输入用例n=0时，表示输入终止，该用例无需处理。  
输出格式

每组测试用例输出两行。

第一行输出”Test case \#k”，其中k是测试用例的编号，从1开始。

第二行输出“Total explored area：a”，其中a是总地图面积（即此测试用例中所有矩形的面积并，注意如果一片区域被多个地图包含，则在计算总面积时只计算一次），精确到小数点后两位数。

在每个测试用例后输出一个空行。  
数据范围

1≤n≤100  
,  
0≤x1<x2≤100000,  
0≤y1<y2≤100000

输入样例：

2  
10 10 20 20  
15 15 25 25.5  
0

输出样例：

Test case \#1  
Total explored area: 180.00

分析：  
今天一个上午，才写了这一个题目。唉 菜鸡的acm呀。  
这个题目应该是扫描线的入门题了吧。我也不清楚。总之，是我的第一道扫描线的题目。  
[https://blog.csdn.net/riba2534/article/details/76851233][https_blog.csdn.net_riba2534_article_details_76851233]　  
强烈安利这个博客了。  
我在说下我的理解。

我们从下往上扫描。扫到一条线，我们要统计的是，在这根线上的长度。那么整个问题就在于我们如何知道长度。为了达到这个目的，我们需要借助线段树。我们用线段树来维护这个区间出现的次数（可理解为此时这个区间是否需要要计算的范围内）。  
可是线段树的叶子结点如（3，3）这个代表什么意思呢？难道是表示3这个位置出现了多少次吗？  
其实不然，线段树维护的内容是一段区间，也就是说（3，3）表示从左往右数过去的第三个区间。（注：如果一共ｍ个点，那就只有ｍ－１个区间）。理解了这里，就明白了为什么一开始查询的时候R-1了。算的时候R+1了。

#include"stdio.h"
    #include"string.h"
    #include"algorithm"
    using namespace std;
    
    typedef struct Line
    {
        double x1,x2,y;
        int mark;
        Line(){};
        Line(double a,double b,double c,int id)
        {
            x1 = a; x2 = b; y = c; mark = id;
        }
    }Line;
    
    typedef struct Node
    {
        int l,r;
        int cnt;
        double len;
        Node(){}
        Node(int a,int b,double c)
        {
            l = a; r = b; cnt = c;
        }
    }Node;
    
    int n;
    Node node[1010];
    Line line[1010];
    double dis[1010];
    int top,line_num;
    
    int cmp(Line a,Line b)
    {
        return a.y < b.y;
    }
    
    void Build_Tree(int id,int l,int r)
    {
        node[id].l = l; node[id].r = r;
        node[id].cnt = 0; node[id].len = 0;
        if(l == r)  return;
        int mid = (l + r) >> 1;
        Build_Tree(id << 1,l,mid);
        Build_Tree(id << 1 | 1,mid + 1,r);
    }
    
    void get_len(int id)
    {
        if(node[id].cnt >= 1) node[id].len = dis[node[id].r + 1] - dis[node[id].l];
        else node[id].len = node[id << 1].len + node[id << 1 | 1].len;
       // printf("id = %d len = %.2lf\n",id,node[id].len);
    }
    
    void Update(int id,int l,int r,int val)
    {
        int L = node[id].l;
        int R = node[id].r;
        if(l <= L && r >= R)
        {
            node[id].cnt += val;
            get_len(id);
            return ;
        }
        int mid = (L + R) >> 1;
        if(l <= mid) Update(id << 1,l,r,val);
        if(r > mid) Update(id << 1 | 1 ,l,r,val);
        get_len(id);
    }
    
    int main()
    {
        int cnt = 1;
        while(~scanf("%d",&n))
        {
            if(n == 0) break;
            line_num = 0; top = 0;
            printf("Test case #%d\n",cnt ++);
            for(int i = 1; i <= n; i ++)
            {
                double x1,y1,x2,y2;
                scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
                line[++ line_num] = {x1,x2,y1,1};
                line[++ line_num] = {x1,x2,y2,-1};
                dis[++top] = x1;
                dis[++top] = x2;
            }
            sort(dis + 1,dis + 1 + top);
            sort(line + 1,line + 1 + line_num,cmp);
            top = unique(dis + 1,dis + 1 + top) - dis;
            Build_Tree(1,0,top);
            double sum = 0;
           /* for(int i = 1; i < top; i ++)
                printf("%.0lf ",dis[i]);
            printf("\n");*/
            for(int i = 1; i < line_num; i ++)
            {
                int l = lower_bound(dis + 1,dis + top,line[i].x1) - dis;
                int r = lower_bound(dis + 1,dis + top,line[i].x2) - dis - 1;///因为维护的是一个区间
                //printf("x1 = %.0lf x2 = %.0lf l = %d r = %d\n",line[i].x1,line[i].x2,l,r);
                Update(1,l,r,line[i].mark);
                sum += (line[i + 1].y - line[i].y) * node[1].len;
            }
            printf("Total explored area: %.2lf\n",sum);
        }
    }

[80x15.png]: https://i.creativecommons.org/l/by-sa/4.0/80x15.png
[80x15.png 1]: http://creativecommons.org/licenses/by-sa/4.0/
[https_www.acwing.com_problem_content_249]: https://www.acwing.com/problem/content/249/
[https_blog.csdn.net_riba2534_article_details_76851233]: https://blog.csdn.net/riba2534/article/details/76851233