POJ 1151 Atlantis_刘文蔚 acm-程序员宅基地

技术标签: 线段树  扫描线  ACM题目  poj  离散化  

首先,我得吐个槽。陶叔果然是个诚实的孩子,今天的题简直坑爆了好么?

先说A题,翻了一遍题目,觉得A题(SPOJ SUB_PROB)就是个KMP的模板题,心中大喜,套模板,欲A之,怎奈何居然是WA(我还提交了三遍T_T,再不济你给个TLE我也可以接受啊)。于是重新读题,发现应该拿AC自动机来搞!!!瞄一眼Rank,分析一下局势,决定不理A题了,开了E题(Aizu 0024)。

由于E题是签到水题(按照陶叔的话来说,什么是签到题捏?签到题就是你A了以后能证明你来了的题~),果断AC。接着顺手开了F题(CodeForces 81A),发现F题也很水,是道堆栈的模拟题,以前有做过类似的题目,轻松A掉。看看表才过了不到一个小时,暗自感叹今天运气还是不错滴,喝口水,养个神,开D题(UVA 10319)。

由于英语太渣,读题貌似出现了错误,天真的以为是DFS,开心的码完代码,提交,WA。正在郁闷的时候,看到了陶叔良心发现在公告里给了Hint,尼玛,2-SAT!思路差了八十条街,而且最坑爹的是,我读错题的DFS样例居然过了!于是心情默默的不好了,关了OJ,开始各种骚扰刘文蔚学长。。。。。。

比完赛之后仔细看了看,其实C题(SPOJ RATING)挺好搞的,就是题目写得不是特别顺眼,一开始要是选这道的话,还是有可能A掉的~

好吧,吐完槽了,开始写正经东西,线段树的离散化和扫描线。

POJ上有一道题很经典,算是线段树的进阶吧,大家一起来看一下。

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

题目意思很简单,就是让你求矩形的面积,重合的部分只算一次。解题的步骤大体来说分为三步:

1)输入数据,建树。

2)离散化:将所有的x轴坐标存在一个数组里。

3)扫描线:从下到上扫描,更新区间计数。

图片来自:红黑联盟-kk303




下面是完整的代码:

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define MAXN 405
using namespace std;

struct node
{
      double l,r,y;//左端点,右端点,y轴高度
      int tp;//上下水平线标记
      bool operator < (node a) const// < 运算符重载,sort函数使用
      {
            return y < a.y;
      }
}line[MAXN << 2];

int n;
double X[MAXN << 2],Times[MAXN << 2],sum[MAXN];

int b_search(double x)//区间查找
{
      int l,r,mid;
      l = 0,r = n + 1;
      while (r - l > 1)
      {
            mid=(l + r) >> 1;
            if (X[mid] <= x) l = mid;
               else r = mid;
      }
      return l;//返回离散化的区间
}

void update(int x,int c,int l,int r,int now)
{
      if (l == r)
      {
            Times[x] += c;//区间计数修改
            if (Times[x]) sum[now]=X[x+1]-X[x]; //若区间计数为正,得到区间长度
            if (!Times[x]) sum[now]=0;//若区间计数为零,不计入长度
            return;
      }
      int mid = (l + r )/ 2;
      if (x <= mid) update(x,c,l,mid,now << 1);
      if (mid < x)  update(x,c,mid + 1,r,(now << 1) | 1);
      sum[now] = sum[now << 1] + sum[(now << 1) | 1];
      return;
}
int main()
{
      int i,j,T=0;
      double ans=0;
      while (~scanf("%d",&n) && n)
      {
            int num=0;
            for (i=1;i<=n;i++)
            {
                   double x1,y1,x2,y2;
                   scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);//录入矩形的对角线端点

                   line[i*2-1].y = y1;//矩形水平线的y轴坐标
                   line[i*2-1].l = x1;//水平线的左端点
                   line[i*2-1].r = x2;//水平线的右端点
                   line[i*2-1].tp = 1;//下水平线标记

                   line[i*2].y = y2;//矩形水平线的y轴坐标
                   line[i*2].l = x1;//水平线的左端点
                   line[i*2].r = x2;//水平线的右端点
                   line[i*2].tp = -1;//上水平线标记

                   X[++num]=x1;//矩阵的左端点
                   X[++num]=x2;//矩阵的右端点
            }
            
            ans = 0;
            n = n * 2;//每个矩阵都有上下水平线
            
            sort(X + 1,X + 1 + num);//将所有X坐标从小到大排序
            sort(line + 1,line + 1 + n);//将所有line按Y坐标从小到大排序

            memset(sum,0,sizeof(sum));//扫描线扫到的合法长度
            memset(Times,0,sizeof(Times));//区间的计数数组

            for (i = 1;i <= n;i++)
            {
                   ans += sum[1] * (line[i].y - line[i - 1].y);//面积 = 每一段合法长度 * 高度
                   int l,r;
                   l = b_search(line[i].l);//离散化,获取区间
                   r = b_search(line[i].r) - 1;//离散化,获取区间
                   for (j = l;j <= r;j++)
                        update(j,line[i].tp,1,n-1,1);//扫描线更新操作
            }
            printf("Test case #%d\nTotal explored area: %.2f\n\n",++T,ans);
      }
      return 0;
}


版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/spirtsong/article/details/38461095

智能推荐

攻防世界_难度8_happy_puzzle_攻防世界困难模式攻略图文-程序员宅基地

文章浏览阅读645次。这个肯定是末尾的IDAT了,因为IDAT必须要满了才会开始一下个IDAT,这个明显就是末尾的IDAT了。,对应下面的create_head()代码。,对应下面的create_tail()代码。不要考虑爆破,我已经试了一下,太多情况了。题目来源:UNCTF。_攻防世界困难模式攻略图文

达梦数据库的导出(备份)、导入_达梦数据库导入导出-程序员宅基地

文章浏览阅读2.9k次,点赞3次,收藏10次。偶尔会用到,记录、分享。1. 数据库导出1.1 切换到dmdba用户su - dmdba1.2 进入达梦数据库安装路径的bin目录,执行导库操作  导出语句:./dexp cwy_init/[email protected]:5236 file=cwy_init.dmp log=cwy_init_exp.log 注释:   cwy_init/init_123..._达梦数据库导入导出

js引入kindeditor富文本编辑器的使用_kindeditor.js-程序员宅基地

文章浏览阅读1.9k次。1. 在官网上下载KindEditor文件,可以删掉不需要要到的jsp,asp,asp.net和php文件夹。接着把文件夹放到项目文件目录下。2. 修改html文件,在页面引入js文件:<script type="text/javascript" src="./kindeditor/kindeditor-all.js"></script><script type="text/javascript" src="./kindeditor/lang/zh-CN.js"_kindeditor.js

STM32学习过程记录11——基于STM32G431CBU6硬件SPI+DMA的高效WS2812B控制方法-程序员宅基地

文章浏览阅读2.3k次,点赞6次,收藏14次。SPI的详情简介不必赘述。假设我们通过SPI发送0xAA,我们的数据线就会变为10101010,通过修改不同的内容,即可修改SPI中0和1的持续时间。比如0xF0即为前半周期为高电平,后半周期为低电平的状态。在SPI的通信模式中,CPHA配置会影响该实验,下图展示了不同采样位置的SPI时序图[1]。CPOL = 0,CPHA = 1:CLK空闲状态 = 低电平,数据在下降沿采样,并在上升沿移出CPOL = 0,CPHA = 0:CLK空闲状态 = 低电平,数据在上升沿采样,并在下降沿移出。_stm32g431cbu6

计算机网络-数据链路层_接收方收到链路层数据后,使用crc检验后,余数为0,说明链路层的传输时可靠传输-程序员宅基地

文章浏览阅读1.2k次,点赞2次,收藏8次。数据链路层习题自测问题1.数据链路(即逻辑链路)与链路(即物理链路)有何区别?“电路接通了”与”数据链路接通了”的区别何在?2.数据链路层中的链路控制包括哪些功能?试讨论数据链路层做成可靠的链路层有哪些优点和缺点。3.网络适配器的作用是什么?网络适配器工作在哪一层?4.数据链路层的三个基本问题(帧定界、透明传输和差错检测)为什么都必须加以解决?5.如果在数据链路层不进行帧定界,会发生什么问题?6.PPP协议的主要特点是什么?为什么PPP不使用帧的编号?PPP适用于什么情况?为什么PPP协议不_接收方收到链路层数据后,使用crc检验后,余数为0,说明链路层的传输时可靠传输

软件测试工程师移民加拿大_无证移民,未受过软件工程师的教育(第1部分)-程序员宅基地

文章浏览阅读587次。软件测试工程师移民加拿大 无证移民,未受过软件工程师的教育(第1部分) (Undocumented Immigrant With No Education to Software Engineer(Part 1))Before I start, I want you to please bear with me on the way I write, I have very little gen...

随便推点

Thinkpad X250 secure boot failed 启动失败问题解决_安装完系统提示secureboot failure-程序员宅基地

文章浏览阅读304次。Thinkpad X250笔记本电脑,装的是FreeBSD,进入BIOS修改虚拟化配置(其后可能是误设置了安全开机),保存退出后系统无法启动,显示:secure boot failed ,把自己惊出一身冷汗,因为这台笔记本刚好还没开始做备份.....根据错误提示,到bios里面去找相关配置,在Security里面找到了Secure Boot选项,发现果然被设置为Enabled,将其修改为Disabled ,再开机,终于正常启动了。_安装完系统提示secureboot failure

C++如何做字符串分割(5种方法)_c++ 字符串分割-程序员宅基地

文章浏览阅读10w+次,点赞93次,收藏352次。1、用strtok函数进行字符串分割原型: char *strtok(char *str, const char *delim);功能:分解字符串为一组字符串。参数说明:str为要分解的字符串,delim为分隔符字符串。返回值:从str开头开始的一个个被分割的串。当没有被分割的串时则返回NULL。其它:strtok函数线程不安全,可以使用strtok_r替代。示例://借助strtok实现split#include <string.h>#include <stdio.h&_c++ 字符串分割

2013第四届蓝桥杯 C/C++本科A组 真题答案解析_2013年第四届c a组蓝桥杯省赛真题解答-程序员宅基地

文章浏览阅读2.3k次。1 .高斯日记 大数学家高斯有个好习惯:无论如何都要记日记。他的日记有个与众不同的地方,他从不注明年月日,而是用一个整数代替,比如:4210后来人们知道,那个整数就是日期,它表示那一天是高斯出生后的第几天。这或许也是个好习惯,它时时刻刻提醒着主人:日子又过去一天,还有多少时光可以用于浪费呢?高斯出生于:1777年4月30日。在高斯发现的一个重要定理的日记_2013年第四届c a组蓝桥杯省赛真题解答

基于供需算法优化的核极限学习机(KELM)分类算法-程序员宅基地

文章浏览阅读851次,点赞17次,收藏22次。摘要:本文利用供需算法对核极限学习机(KELM)进行优化,并用于分类。

metasploitable2渗透测试_metasploitable2怎么进入-程序员宅基地

文章浏览阅读1.1k次。一、系统弱密码登录1、在kali上执行命令行telnet 192.168.26.1292、Login和password都输入msfadmin3、登录成功,进入系统4、测试如下:二、MySQL弱密码登录:1、在kali上执行mysql –h 192.168.26.129 –u root2、登录成功,进入MySQL系统3、测试效果:三、PostgreSQL弱密码登录1、在Kali上执行psql -h 192.168.26.129 –U post..._metasploitable2怎么进入

Python学习之路:从入门到精通的指南_python人工智能开发从入门到精通pdf-程序员宅基地

文章浏览阅读257次。本文将为初学者提供Python学习的详细指南,从Python的历史、基础语法和数据类型到面向对象编程、模块和库的使用。通过本文,您将能够掌握Python编程的核心概念,为今后的编程学习和实践打下坚实基础。_python人工智能开发从入门到精通pdf

推荐文章

热门文章

相关标签