正文

hdu 1542 Atlantis(段树&扫描线&面积和)

IP云
IP云V管理员/5 阅读
09/08
提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

Atlantis

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)

Total Submission(s): 6386    Accepted Submission(s): 2814

Problem 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 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
 
Source
Mid-Central European Regional Contest 2000
 
Recommend
linle   |   We have carefully selected several similar problems for you:  1828 1255 1823 

pid=1543" target="_blank">1543

 3333 
 题意：
给你一些矩形和坐标轴平行的矩形。告诉你们他们左下角和右上角的坐标。如今问你。整个坐标面被他们覆盖的面积。
思路：
因为直接找的线段树扫描线的题目。所以也没想其他思路。讲一下为什么能够用扫描线来做吧。首先是面积的求解。

面积=底边长*高。这底边长不一定要求连续。所以假设我们知道某一时刻底边长和高就能够算出面积了。而线段树就能够出色的完毕求出某个时间底边长(x轴被覆盖的长度)。

所以我们仅仅须要把全部平行与x轴的边按高度排序。然后依次插入到线段树中。遇到矩形的下边就增加到线段树中。遇到上边就把相应的下边从线段树中删除。文字可能不是非常好理解。绘图看看就知道了。

具体见代码：

#include<algorithm>
#include<iostream>
#include<string.h>
#include<stdio.h>
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=250;
#define lson L,mid,ls
#define rson mid+1,R,rs
int n,m;
int cov[maxn<<2];
double len[maxn<<2],H[maxn];
struct node
{
double x1,x2,h;
int v;
node(double a=0,double b=0,double c=0,int d=0):x1(a),x2(b),h(c),v(d){}
} seg[maxn];
bool cmp(node a,node b)
{
return a.h<b.h;
}
void init()
{
sort(H,H+m);
m=unique(H,H+m)-H;
}
int Hash(double x)
{
return lower_bound(H,H+m,x)-H;
}
void PushUp(int L,int R,int rt)
{
if(cov[rt])//有标记肯定整块覆盖了
len[rt]=H[R+1]-H[L];
else if(L==R)//没有左右儿子了。len[rt]=0;
else//没有整块覆盖可是被部分覆盖了
len[rt]=len[rt<<1]+len[rt<<1|1];
}
void update(int L,int R,int rt,int l,int r,int d)
{
if(l<=L&&R<=r)
{
cov[rt]+=d;
PushUp(L,R,rt);
return;
}//这样的标记是不用下传的。由于没删除一个上边。一定有一个下边与之相应。int mid=(L+R)>>1,ls=rt<<1,rs=ls|1;
if(l<=mid)
update(lson,l,r,d);
if(r>mid)
update(rson,l,r,d);
PushUp(L,R,rt);
}
int main()
{
int cas=1,i,ptr;
double x1,x2,y1,y2,ans;
while(scanf("%d",&n),n)
{
printf("Test case #%d\n",cas++);
for(i=ptr=0;i<n;i++)
{
scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
H[ptr]=x1;
seg[ptr++]=node(x1,x2,y1,1);
H[ptr]=x2;
seg[ptr++]=node(x1,x2,y2,-1);
}
m=ptr,ans=0;
init();
sort(seg,seg+ptr,cmp);
memset(len,0,sizeof len);
memset(cov,0,sizeof cov);
for(i=0,ptr--;i<ptr;i++)
{
update(0,m-1,1,Hash(seg[i].x1),Hash(seg[i].x2)-1,seg[i].v);//m个结点m-1条线段
ans+=(seg[i+1].h-seg[i].h)*len[1];
}
printf("Total explored area: %.2lf\n\n",ans);
}
return 0;
}

版权声明：本文博客原创文章。博客，未经同意，不得转载。

hdu 1542 Atlantis(段树&amp;扫描线&amp;面积和)的更多相关文章

  1. hdu 1542 Atlantis&lpar;线段树，扫描线&rpar;

    Atlantis Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total S ...

  2. hdu 1542 Atlantis 段树区，并寻求，，，尼玛真坑人数据，不要打开一小阵！

    Atlantis Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total S ...

  3. HDU 1542 - Atlantis - &lbrack;线段树&plus;扫描线&rsqb;

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1542 Time Limit: 2000/1000 MS (Java/Others) Memory Li ...

  4. HDU 1542&period;Atlantis-线段树求矩形面积并&lpar;离散化、扫描线&sol;线段树&rpar;-贴模板

    好久没写过博客了,这学期不是很有热情去写博客,写过的题也懒得写题解.现在来水一水博客,写一下若干年前的题目的题解. Atlantis Time Limit: 2000/1000 MS (Java/Ot ...

  5. HDU 1542 Atlantis &lpar;线段树 &plus; 扫描线 &plus; 离散化&rpar;

    Atlantis Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total S ...

  6. hdu 1542 Atlantis &lpar;线段树扫描线&rpar;

    大意: 求矩形面积并. 枚举$x$坐标, 线段树维护$[y_1,y_2]$内的边是否被覆盖, 线段树维护边时需要将每条边挂在左端点上. #include <iostream> #inclu ...

  7. HDU 1542 Atlantis&lpar;线段树面积并&rpar;

     描述 There are several ancient Greek texts that contain descriptions of the fabled island Atlantis. S ...

  8. POJ 1151 &sol; HDU 1542 Atlantis 线段树求矩形面积并

    题意:给出矩形两对角点坐标,求矩形面积并. 解法:线段树+离散化. 每加入一个矩形,将两个y值加入yy数组以待离散化,将左边界cover值置为1,右边界置为2,离散后建立的线段树其实是以y值建的树,线 ...

  9. &lpar;HDU 1542&rpar; Atlantis 矩形面积并——扫描线

    n个矩形,可以重叠,求面积并. n<=100: 暴力模拟扫描线.模拟赛大水题.(n^2) 甚至网上一种“分块”:分成n^2块,每一块看是否属于一个矩形. 甚至这个题就可以这么做. n<=1 ...

随机推荐

  1. PHP面向对象&lowbar;重载新的方法（parent&colon;&colon;）

    在学习PHP 这种语言中你会发现, PHP中的方法是不能重载的, 所谓的方法重载就是定义相同的方法名,通过“参数的个数“不同或“参数的类型“不 同,来访问我们的相同方法名的不同方法.但是因为PHP是弱 ...

  2. ecshop mobile 文件介绍

    mobile手机端 1.common位置:include\apps\default\common\ function.php show_message 成功跳转页面    其他页面引用  show_m ...

  3. Python中pip版本升级error：You are using pip version 7&period;1&period;2&comma; however version 8&period;1&period;1 is available&period;

    使用pip install安装命令时,会报错:You are using pip version 7.1.2, however version 8.1.1 is available. 尝试了推荐解决办 ...

  4. 黑马程序员&lowbar;Java基础常识

    一.基础常识 1,软件开发 1)什么是软件?软件:一系列按照特定顺序组织的计算机数据和指令的集合. 常见的软件 系统软件 如:DOS,windows,Linux等. 应用软件: 如:扫雷,迅雷,QQ等 ...

  5. python学习之路-13

    SQLAlchemy ORM框架 连表操作 一对多 创建表 指定约束 ForeignKey from sqlalchemy import create_engine from sqlalchemy.e ...

  6. Android MTK平台最完备的开机动画修改教程

    修改手机的开机动画不是什么难事儿. 但修改一款很冷门的"山寨机",就不太好修改第一屏了. 手机是MTK的一款手机,虽然比较贵(价格超过三星Note3),但在我看来跟山寨机木有啥区别 ...

  7. 《了不起的 nodejs》中 TwitterWeb 案例 bug 解决

    了不起的nodejs算是一本不错的入门书,不过书中个别案例存在bug,按照书中源码无法做出和书中相同效果,原本兴奋的心情掺杂着些许失落. 现在我们看一下第七章HTTP,一个 Twitter Web 客 ...

  8. Yii2的mongodb的聚合操作

    最近项目使用到mongodb的聚合操作,但是yii文档中对这方面资料较少,记录下 $where['created_time'] = ['$gt' => "$start_date_str ...

  9. python中logging模块的使用

    一.基本用法 只需要基本的配置,就可以使用了. import logging def fun2(): logging.basicConfig(filename="fun2.log" ...

  10. 华为ensp使用

    网络学习目录 AR是() Auto:自动线 copper:双绞线缆  serial:串行线  pos: 光纤  E1:    ATM:    CTL:       STA:    PC:    MCS ...