hdu1542 Atlantis(扫描线+线段树+离散)矩形相交面积

时间:2022-12-25 18:04:29

题目链接:点击打开链接

题目描写叙述:给定一些矩形,求这些矩形的总面积。假设有重叠。仅仅算一次

解题思路:扫描线+线段树+离散(代码从上往下扫描)

代码:

#include<cstdio>
#include <algorithm>
#define MAXN 110
#define LL ((rt<<1)+1)
#define RR ((rt<<1)+2)
using namespace std;
int n;
struct segment{
double l,r,h;
int f;
bool operator<(const segment& b)const{
return h>b.h;
}
}sg[2*MAXN];
double pos[2*MAXN];
int id;
void addSegment(double x1,double y1,double x2,double y2){
sg[id].l=x1;sg[id].r=x2;
sg[id].h=y1;sg[id].f=1;
pos[id++]=x1;
sg[id].l=x1;sg[id].r=x2;
sg[id].h=y2;sg[id].f=-1;
pos[id++]=x2;
}
int binary(double key,int low,int high){
while(low<=high){
int mid=(low+high)/2;
if(pos[mid]==key)
return mid;
else if(key<pos[mid])
high=mid-1;
else
low=mid+1;
}
return -1;
}
struct Tree{
int l,r;
int cover;
double len;
}tree[8*MAXN];
void build(int rt,int l,int r){
tree[rt].l=l;
tree[rt].r=r;
tree[rt].cover=0;
tree[rt].len=0;
if(l==r-1)
return;
int mid=(l+r)>>1;
build(LL,l,mid);
build(RR,mid,r);
}
void pushup(int rt){
if(tree[rt].cover)
tree[rt].len=pos[tree[rt].r]-pos[tree[rt].l];
else if(tree[rt].l==tree[rt].r-1)
tree[rt].len=0;
else
tree[rt].len=tree[LL].len+tree[RR].len;
}
void update(int rt,int l,int r,int f){
if(tree[rt].l==l&&tree[rt].r==r){
tree[rt].cover+=f;
pushup(rt);
return;
}
int mid=(tree[rt].l+tree[rt].r)>>1;
if(r<=mid)
update(LL,l,r,f);
else if(l>=mid)
update(RR,l,r,f);
else{
update(LL,l,mid,f);
update(RR,mid,r,f);
}
pushup(rt);
}
int main(){
int Case=0;
while(scanf("%d",&n)!=EOF&&n!=0){
id=0;
double x1,y1,x2,y2;
for(int i=0;i<n;++i){
scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
addSegment(x1,y1,x2,y2);
}
n=(n<<1);
sort(sg,sg+n);
sort(pos,pos+n);
int m=1;
for(int i=1;i<n;++i)
if(pos[i]!=pos[i-1])
pos[m++]=pos[i];
build(0,0,m-1);
double ans=0;
int l=binary(sg[0].l,0,m-1);
int r=binary(sg[0].r,0,m-1);
update(0,l,r,sg[0].f);
for(int i=1;i<n;i++){
ans+=(sg[i-1].h-sg[i].h)*tree[0].len;
l=binary(sg[i].l,0,m-1);
r=binary(sg[i].r,0,m-1);
update(0,l,r,sg[i].f);
}
printf("Test case #%d\n",++Case);
printf("Total explored area: %.2f\n\n",ans);
}
return 0;
}

hdu1542 Atlantis(扫描线+线段树+离散)矩形相交面积的更多相关文章

  1. &lbrack;HDU1542&rsqb;Atlantis&lpar;扫描线&plus;线段树&rpar;

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

  2. hdu1542 Atlantis (线段树&plus;扫描线&plus;离散化)

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

  3. &lbrack;POJ1151&rsqb;&lbrack;HDU1542&rsqb;Atlantis(线段树,扫描线)

    英文题面,我就只放个传送门了. Solution  题意是算矩形面积并,这是扫描线算法能解决的经典问题. 算法的大致思想是,把每一个矩形拆成上边和下边(以下称作扫描线),每条扫描线有四个参数l,r,h ...

  4. hdu-1542 Atlantis&lpar;离散化&plus;线段树&plus;扫描线算法&rpar;

    题目链接: Atlantis Time Limit: 2000/1000 MS (Java/Others)     Memory Limit: 65536/32768 K (Java/Others) ...

  5. poj1151 Atlantis——扫描线&plus;线段树

    题目:http://poj.org/problem?id=1151 经典的扫描线问题: 可以用线段树的每个点代表横向被矩形上下边分割开的每一格,这样将一个矩形的出现或消失化为线段树上的单点修改: 每个 ...

  6. POJ 1151 Atlantis &lpar;扫描线&plus;线段树&rpar;

    题目链接:http://poj.org/problem?id=1151 题意是平面上给你n个矩形,让你求矩形的面积并. 首先学一下什么是扫描线:http://www.cnblogs.com/scau2 ...

  7. HDU 1255 覆盖的面积 (扫描线 线段树 离散化 矩形面积并)

    题目链接 题意:中文题意. 分析:纯手敲,与上一道题目很相似,但是刚开始我以为只是把cnt>=0改成cnt>=2就行了,. 但是后来发现当当前加入的线段的范围之前 还有线段的时候就不行了, ...

  8. POJ 1151Atlantis 扫描线&plus;线段树求矩形面积并

    题目链接 #include <iostream> #include <vector> #include <cstdio> #include <cstring& ...

  9. 【POJ1151】Atlantis(线段树,扫描线)

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

随机推荐

  1. 使用ZIM桌面维基做笔记

    最近尝试了使用ZIM做笔记,感觉还不错 ubuntu下直接到软件中心即可安装,或者 sudo apt-get install zim windows下的到此下载http://www.glump.net ...

  2. Oracle11&period;2新特性之listagg函数 (行列转换)

    SELECT regexp_substr('公司1,贵公司2', '[^,]+', 1, LEVEL, 'i') FROM dualCONNECT BY LEVEL <= length('公司1 ...

  3. Python-正则零宽断言及命名捕获&lpar;类PHP&rpar;

    (一)零宽断言 说明:本文的例子使用python描述      首先说明一下什么是零宽断言,所谓零宽断言就是并不去真正的匹配字符串文本,而仅仅是匹配对应的位置.      正则表达式中有很多这样的断言 ...

  4. 关于Thread的Runnable和Callable接口

    其实非常简单:其实他们的区别就是Callable有返回值并且可以抛出异常. /** * Represents a command that can be executed. Often used to ...

  5. 【环境搭建】使用Jekyll搭建Github博客

    前言 昨天花了差不多一天的时间,使用Jekyll搭建起了一套Github博客,感觉不错,也特将搭建过程记录下来,方便有需要的朋友自行搭建. 搭建步骤 本环境是在Linux环境下搭建完成的 安装前建议使 ...

  6. c&num; 替换所有中文、标点符号,全角转半角

    private void btnStart_Click(object sender, EventArgs e) { var srcWords = ToDBC(txtSrc.Text.Trim()); ...

  7. Python项目读取配置的几种方式

    1. 将配置写在Python文件中 配置文件(config.py 或 settings.py) 通常放置在程序源代码的目录,方便引用 配置文件 # settings.py class Config(o ...

  8. Spring Boot Starters 列表

    Spring Boot application starters 名称 描述 Pom spring-boot-starter 核心starter,包括自动配置支持,日志和YAML Pom spring ...

  9. OGG 问题

    1.启动复制时报 "ERROR OGG-15050 Oracle GoldenGate Delivery, l***.prm: Error loading Java VM runtime l ...

  10. php 获取当前完整url地址

    echo $url = $_SERVER["REQUEST_SCHEME"].'://'.$_SERVER["SERVER_NAME"].$_SERVER[&q ...