poj 1151 (未完成) 扫描线 线段树 离散化

时间:2022-08-31 11:51:42
#include<iostream>
#include<vector>
#include<cmath>
#include<algorithm>
using namespace std;
#define y1 y11
#define ls rt<<1,l,m
#define rs rt<<1|1,m+1,r
const int maxn=1e3+;
double x1[maxn];
double y1[maxn];
double x2[maxn];
double y2[maxn];
vector<double> vx;
vector<double> vy;
double x[maxn];
double y[maxn];
struct node { int yl,yr,k; }pp[maxn];
vector<node> vxxx[maxn];
double tree[*maxn];
double ans[*maxn];
int lazy[*maxn]; int tot=;
void push_up(int rt) { tree[rt]=tree[rt<<]+tree[rt<<|]; }
//void push_down(int rt,int len) { lazy[rt<<1]+=lazy[rt]; lazy[rt<<1|1]+=lazy[rt]; lazy[rt]=0; }
void build(int rt,int l,int r)
{
if(l==r) { tot++; tree[l]=vy[tot]-vy[tot-]; return ; }
int m=(l+r)>>; build(ls); build(rs);push_up(rt);
}
void update(int p,int delta,int rt,int l,int r)
{
if(l==r) { tree[rt]+=delta; return ; }
int m=(l+r)>>;
if(p<=m)update(p,delta,ls);
else update(p,delta,rs);
push_up(rt);
}
void Update(int L,int R,int delta,int rt,int l,int r)
{
if(L<=l&&r<=R) { lazy[rt]+=delta; return ; }
if(lazy[rt]) push_down(rt,r-l+);
int m=(l+r)>>;
if(L<=m)Update(L,R,delta,ls);
if(R>m)Update(L,R,delta,rs);
push_up(rt);
}
int main()
{
int cnt=;
int n;
while()
{
scanf("%d",&n); if(n==) break;
for(int i=;i<=n;i++) scanf("%lf %lf %lf %lf",&x1[i],&y1[i],&x2[i],&y2[i]);
for(int i=;i<=n;i++)
{
vx.push_back(x1[i]);
vx.push_back(x2[i]);
vy.push_back(y1[i]);
vy.push_back(y2[i]);
}
sort(vx.begin(),vx.end()); vx.erase(unique(vx.begin(),vx.end()),vx.end());
for(int i=;i<vx.size();i++) x[i]=vx[i];
sort(vy.begin(),vy.end()); vy.erase(unique(vy.begin(),vy.end()),vy.end());
for(int i=;i<vy.size();i++) y[i]=vy[i];
for(int i=;i<=n;i++)
{
int k=lower_bound(vx.begin(),vx.end(),x1[i])-vx.begin();
node p; p.yl=y1[i]; p.yr=y2[i]; p.k=;
vxxx[k].push_back(p);
k=lower_bound(vx.begin(),vx.end(),x2[i])-vx.begin();
p.k=-;
vxxx[k].push_back(p);
}
int m=vy.size()-;
build(,,m);
double ans=;
for(int i=;i<vx.size();i++)
{
if(i==)
{
for(int j=;j<=vxx[i].size();j++)
{
node p=vxxx[i][j];
int l=lower_bound(vy.begin(),vy.end(),p.yl)-vy.begin();
int r=lower_bound(vy.begin(),vy.end(),p.yr)-vy.begin();
update(l,r,p.k,,,m);
}
}
}
}
}

poj 1151 (未完成) 扫描线 线段树 离散化的更多相关文章

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

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

  2. POJ 1151:Atlantis 线段树&plus;扫描线

    Atlantis Time Limit: 1000MS   Memory Limit: 10000K Total Submissions: 19374   Accepted: 7358 Descrip ...

  3. 矩形面积并-扫描线 线段树 离散化 模板-poj1151 hdu1542

    今天刚看到这个模板我是懵逼的,这个线段树既没有建树,也没有查询,只有一个update,而且区间成段更新也没有lazy标记....研究了一下午,我突然我发现我以前根本不懂扫描线,之所以没有lazy标记, ...

  4. POJ 1151 Atlantis(线段树-扫描线,矩形面积并)

    题目链接:http://poj.org/problem?id=1151 题目大意:坐标轴上给你n个矩形, 问这n个矩形覆盖的面积 题目思路:矩形面积并. 代码如下: #include<stdio ...

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

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

  6. BZOJ 1645&colon; &lbrack;Usaco2007 Open&rsqb;City Horizon 城市地平线 扫描线 &plus; 线段树 &plus; 离散化

    Code: #include<cstdio> #include<algorithm> #include<string> #define maxn 1030000 # ...

  7. 【POJ 2482】 Stars in Your Window(线段树&plus;离散化&plus;扫描线)

    [POJ 2482] Stars in Your Window(线段树+离散化+扫描线) Time Limit: 1000MS   Memory Limit: 65536K Total Submiss ...

  8. HDU 3265&sol;POJ 3832 Posters(扫描线&plus;线段树)(2009 Asia Ningbo Regional)

    Description Ted has a new house with a huge window. In this big summer, Ted decides to decorate the ...

  9. POJ 2528 Mayor&&num;39&semi;s posters&lpar;线段树&plus;离散化&rpar;

    Mayor's posters 转载自:http://blog.csdn.net/winddreams/article/details/38443761 [题目链接]Mayor's posters [ ...

随机推荐

  1. 【转】linux sort 命令详解

    sort是在Linux里非常常用的一个命令,管排序的,集中精力,五分钟搞定sort,现在开始! 1 sort的工作原理 sort将文件的每一行作为一个单位,相互比较,比较原则是从首字符向后,依次按AS ...

  2. 基础2&period;通过Ajax获得servlet数据(最基础)

    案列一:从服务器的得到输出的数据 Jsp界面 <script type="text/javascript" src="test.js"></s ...

  3. 清除文件夹下的SVN信息

    Windows Registry Editor Version 5.00 [HKEY_LOCAL_MACHINE/SOFTWARE/Classes/Folder/shell/清除SVN信息] @=&q ...

  4. Spring学习笔记之二----基于XML的Spring AOP配置

    在Spring配置文件中,通常使用<aop:config>元素来设置AOP,其中应包括: <aop:aspect>指定aspect,aspect是一个POJO类,包含了很多的a ...

  5. PHP基础教程-54课-问题

    question: $arr = array(1,2,3,4); /*如何通过foreach 将数组变成 $arr = arry(2,4,6,8) */ 起初用: $arr = array(1,2,3 ...

  6. web前端基础篇⑤

    1.雪碧图技术(精灵图)sprite cpmpass-合并2.兼容性:1.reset充值技术,normalize技术2.加前缀-webkit —mom -ms— -o-3.<!Doctype&g ...

  7. hadoop第一课

    Hadoop基本概念 在当下的IT领域,大数据很"热",实现大数据场 景的Hadoop系列产品更"热". Hadoop是一个开源的分布式系统基础架构,由 Apa ...

  8. AICODER官方小程序和公众号上线了

    小伙伴们,新年好. 在新的一年里,AICODER将继续为大家提供优质的视频资源,为大家提供一个优质的问题解答平台,并且开始提供优质的职业提升类的优质培训资源. 感谢各位一直以来的支持和关注.请加一下A ...

  9. java通过反射拷贝两个对象的同名同类型变量

    深拷贝和浅拷贝 首先对象的复制分为深拷贝和浅拷贝,关于这两者的区别,简单来说就是对于对象的引用,在拷贝的时候,是否会新开辟一块内存,还是直接复制引用. 两者的比较也有很多,具体可以看这篇文章: htt ...

  10. 数据库与java的连接

    jdbc: java database connection,也就是java的数据库连接. 作用: 完成数据库数据和内存数据的交互. 为了屏蔽不同数据库的差异,在内存和各种数据库之间建立了一个接口标准 ...