文档章节

P - Atlantis (线段树+扫描线)

o
 osc_fmg49rzg
发布于 2019/03/20 09:28
字数 926
阅读 18
收藏 0

精选30+云产品,助力企业轻松上云!>>>

 
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. 

InputThe 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.OutputFor 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 
题解:扫描线常规操作,如果不会先看大神的讲解再来:https://blog.csdn.net/xianpingping/article/details/83032798
#include<bits/stdc++.h>
using namespace std;
const int maxn=205;
double x[maxn];
struct node
{
    double l,r,h;
    int d;
    bool operator < (const node &a)const//按纵坐标从小到大排序
    {
        return h<a.h;
    }
}line[maxn];
int cnt[maxn<<2];//cnt[rt]表示该节点的覆盖次数,只要不为0就是被覆盖过
double sum[maxn<<2];//线段树sum[rt]中每一个节点都是一个区间,sum[rt]表示该节点区间中的总有效覆盖长度
double area;
void pushup(int l,int r,int rt)
{
    if(cnt[rt])//如果该节点(就是一个区间)全部被覆盖,那么sum就是这个区间的长度了~
        sum[rt]=x[r+1]-x[l];//x的下标是点,对于线段树的一个区间要进行右边下标+1再减去左边
    else    //否则要进行左右儿子的加和,因为不连续啊~
        sum[rt]=sum[rt*2]+sum[rt*2+1];
}
void update(int L,int R,int v,int l,int r,int rt)//在L,R区间覆盖次数加上v,即如果v为1就加1,为-1就减1
{
    if(L<=l&&R>=r)
    {
        cnt[rt]+=v;
        pushup(l,r,rt);//改变了cnt数组后要重新pushup
        return ;
    }
    int mid=(l+r)/2;//下面常规操作~
    if(L<=mid)
        update(L,R,v,l,mid,rt*2);
    if(R>=mid+1)
        update(L,R,v,mid+1,r,rt*2+1);
    pushup(l,r,rt);
}
int main()
{
    int t,k=1;
    while(cin>>t&&t)
    {
        memset(cnt,0,sizeof(cnt));//初始化全部为0
        memset(sum,0,sizeof(sum));
        area=0;     //求得面积
        int n=0,m=0;//x数组得最大元素个数,line数组得最大元素个数
        for(int i=1;i<=t;i++)//记录信息
        {
            double x1,y1,x2,y2;
            cin>>x1>>y1>>x2>>y2;
            x[++n]=x1;
            x[++n]=x2;
            line[++m]=(node){x1,x2,y1,1};
            line[++m]=(node){x1,x2,y2,-1};
        }
        sort(x+1,x+1+n);//对x数组从小打大排序
        sort(line+1,line+1+m);//对line扫描线数组按高度(即y)从小到大排序
        int r=unique(x+1,x+1+n)-x-1;//r个不同的x将一条线段分成r-1个小区间,这也是后面查询总区长度是1到r-1和R--的原因
        for(int i=1;i<m;i++)//这里是对扫描线进行扫描~,扫描m-1次即可
        {
            int L=lower_bound(x+1,x+r+1,line[i].l)-x;
            int R=lower_bound(x+1,x+r+1,line[i].r)-x;
            R--;//每一个节点是一个区间,这里是将点转化为区间的操作
            update(L,R,line[i].d,1,r-1,1);
            area+=sum[1]*(line[i+1].h-line[i].h);//用总有效长度乘上两条扫描线之间的距离即得到该块面积
        }
        printf("Test case #%d\nTotal explored area: %.2f\n\n",k++,area);
    }
    return 0;
}

 

 
o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
『线段树及扫描线算法 Atlantis』

<font size=3 face="微软雅黑"> <更新提示> 入门看这边『线段树 Segment Tree』。 <第一次更新> </font> <font size=3 face="微软雅黑"> <正文> 扫描线 扫描线是一种解决一类平面内统计问题的......

osc_rlzm0f6h
2019/05/18
4
0
[poj1151]Atlantis & [poj1177]picture(扫描线)

版权声明:本文为博主原创文章,转载请附上原博客链接。 https://blog.csdn.net/CABI_ZGX/article/details/82799576 玩一玩扫描线,这个东西还是很强力的,而且容易yy。但是就是细节很多,所...

_Mocha_
2018/09/21
0
0
【POJ1151】Atlantis(线段树,扫描线)

#【POJ1151】Atlantis(线段树,扫描线) 题面 Vjudge 题解 学一学扫描线其实很简单啦这道题目要求的就是若干矩形的面积和 把扫描线平行于某个轴扫过去(我选的平行$y$轴扫)这样只需要求出每...

osc_dw190tw4
2018/02/06
3
0
矩形面积并、矩形面积交、矩形周长并(线段树、扫描线总结)(转载)

HDU 1542 [POJ 1151] Atlantis (矩形面积并) 题意: 求N<=100个矩形的面积并 分析: 离散化: 这些技巧都是老生常谈的了, 不然浮点数怎么建树, 离散化x坐标就可以了 扫描线: 首先把矩形按y轴分...

osc_a63j46zs
2018/02/12
15
0
POJ 1151 Atlantis 线段树+扫描线+离散化+延迟更新

POJ 1151 最先用矩形分割过了,然后才开始研究扫描线。说实话扫描线确实是一个比较巧妙的思路,但网上讲解扫描线的也比较少…… 贴个连接(这片博文引导我理解了扫描线):http://www.cnblogs....

WangDylan
2013/05/01
509
0

没有更多内容

加载失败,请刷新页面

加载更多

在Bash脚本中,如果发生某种情况,如何退出整个脚本?

问题: I'm writing a script in Bash to test some code. 我正在Bash中编写脚本来测试一些代码。 However, it seems silly to run the tests if compiling the code fails in the first pl......

技术盛宴
35分钟前
18
0
Windows安装Python+OpenCV

1、更新PyCharm中pip来源,使用清华和阿里云:https://pypi.tuna.tsinghua.edu.cn/simple/ http://mirrors.aliyun.com/pypi/simple/ 2、PyCharm查看已安装packets,添加新的安装包,从pip云端...

极客行
58分钟前
17
0
tomcat8配置虚拟目录,实现一个tomcat运行两个项目, tomcat配置URL不区分大小写

<?xml version="1.0" encoding="UTF-8"?><!-- Licensed to the Apache Software Foundation (ASF) under one or more contributor license agreements. See the NOTICE file distri......

青峰Jun19er
今天
19
0
HBase和MySQL存储方式的差别?或者说是,行存储和列存储的区别?

HBase借鉴列存储的思想,但是最底层依然是依靠键值对来存储数据,HBase为非关系型数据库 而MySQL则是行存储,MySQL为关系型数据库 写过程 行存储因为数据是连续的,所以只需要进行追加即可;...

其乐m
今天
25
0
一个老程序员在互联网寒冬下的感悟

1. 你千万不要认为学习技术就可以换来稳定的生活和高的薪水待遇,你更不要认为那些从事市场开发,跑腿的人,没有前途。 不清楚你是不是知道,咱们中国有相当大的一部分软件公司,他们的软件开...

北柠Java
今天
39
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部