poj1177--Picture--扫描线

2024-06-12 12:18
文章标签 扫描线 picture poj1177

本文主要是介绍poj1177--Picture--扫描线,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

思想和前段时间的1151差不多,


都是通过扫描线的移动来计算周长,不同的是要通过对与x轴平行的扫描线扫一次,与y轴平行的扫描线扫一次,


扫描两次得到周长。


变量last为记录上一次扫描得到的长度,sum为记录这一次总共扫描得到的长度。


abs(sum-last)即为所扫描到的一次长度,


非常耐人寻味的是,我询问学长为什么可以这样做的时候,学长提到了一个投影的概念,即投影的变化反应长度的变化,


智商拙计。。。。还在思考ing。


据说这道题还可以通过一次扫描顺带扫描y轴得到周长(记录x轴上分割开来的即不连续线段个数,乘以2就是y的个数。PS:这个有种特殊情况不满足,即一个矩形包含一个小矩形的情况),改天再碰扫描线的时候再来看看吧。


一下是代码:可与poj1151比较,是我的代码风格= =!


#include <cstdio>
#include <algorithm>
using namespace std;
const int maxnum=10010;typedef struct
{int l,r;int ll,rr;int cover;int len;
}Nodex;typedef struct
{int h,d;int hh,dd;int cover;int len;
}Nodey;typedef struct
{int flag; //记录出边还是入边,入边为1,出边为-1.int x1,x2,y;
}scanlen_x;typedef struct
{int flag; //记录出边还是入边,入边为1,出边为-1int y1,y2,x;
}scanlen_y;Nodex treex[maxnum*4];
Nodey treey[maxnum*4];
scanlen_x scanx[maxnum];
scanlen_y scany[maxnum];
int x[maxnum];
int y[maxnum];bool mycomparex(scanlen_x a,scanlen_x b)
{return a.y<b.y;
}bool mycomparey(scanlen_y a,scanlen_y b)
{return a.x<b.x;
}void buildx(int root,int l,int r)
{treex[root].l=l;treex[root].r=r;treex[root].ll=x[l];treex[root].rr=x[r];treex[root].cover=0;treex[root].len=0;if(l+1==r) return;int mid=(l+r)>>1;buildx(root<<1,l,mid);buildx(root<<1|1,mid,r);
}void buildy(int root,int l,int r)
{treey[root].d=l;treey[root].h=r;treey[root].dd=y[l];treey[root].hh=y[r];treey[root].cover=0;treey[root].len=0;if(l+1==r) return;int mid=(l+r)>>1;buildy(root<<1,l,mid);buildy(root<<1|1,mid,r);
}void updatex(scanlen_x a,int l,int r,int root)
{if(l==treex[root].ll&&r==treex[root].rr)treex[root].cover+=a.flag;else{int mid=(treex[root].l+treex[root].r)>>1;if(l>=x[mid]) updatex(a,l,r,root<<1|1);else if(r<=x[mid]) updatex(a,l,r,root<<1);else{updatex(a,l,x[mid],root<<1);updatex(a,x[mid],r,root<<1|1);}}if(treex[root].cover)//以下更新root的len,即扫描到的总长度treex[root].len=treex[root].rr-treex[root].ll;else if(treex[root].l+1==treex[root].r)treex[root].len=0;elsetreex[root].len=treex[root<<1].len+treex[root<<1|1].len;
}
void updatey(scanlen_y a,int d,int h,int root)
{if(d==treey[root].dd&&h==treey[root].hh)treey[root].cover+=a.flag;else{int mid=(treey[root].d+treey[root].h)>>1;if(d>=y[mid]) updatey(a,d,h,root<<1|1);else if(h<=y[mid]) updatey(a,d,h,root<<1);else{updatey(a,d,y[mid],root<<1);updatey(a,y[mid],h,root<<1|1);}}//以下更新root的len,即扫描到的总长度.if(treey[root].cover)treey[root].len=treey[root].hh-treey[root].dd;else if(treey[root].d+1==treey[root].h)treey[root].len=0;elsetreey[root].len=treey[root<<1].len+treey[root<<1|1].len;
}
int main()
{int n;while(scanf("%d",&n)==1){int i,m=1,k=1;for(i=1;i<=n;++i){int x1,y1,x2,y2;scanf("%d%d%d%d",&x1,&y1,&x2,&y2);scanx[m].x1=x1;scanx[m].x2=x2;scanx[m].y=y1;scanx[m].flag=1;x[m++]=x1;scanx[m].x1=x1;scanx[m].x2=x2;scanx[m].y=y2;scanx[m].flag=-1;x[m++]=x2;scany[k].y1=y1;scany[k].y2=y2;scany[k].x=x1;scany[k].flag=1;y[k++]=y1;scany[k].y1=y1;scany[k].y2=y2;scany[k].x=x2;scany[k].flag=-1;y[k++]=y2;}--m,--k;sort(scanx+1,scanx+m+1,mycomparex);sort(x+1,x+m+1);sort(scany+1,scany+k+1,mycomparey);sort(y+1,y+k+1);int o=2,p=2;for(i=2;i<=m;++i)if(x[i]!=x[i-1]) x[o++]=x[i];for(i=2;i<=k;++i)if(y[i]!=y[i-1]) y[p++]=y[i];--o,--p;buildx(1,1,o);//在x轴建立线段树buildy(1,1,p);//在y轴建立线段树int ans=0,last=0;for(i=1;i<=m;++i){updatex(scanx[i],scanx[i].x1,scanx[i].x2,1);ans+=abs(treex[1].len-last);last=treex[1].len;}last=0;for(i=1;i<=k;++i){updatey(scany[i],scany[i].y1,scany[i].y2,1);ans+=abs(treey[1].len-last);last=treey[1].len;}printf("%d\n",ans);}return 0;
}




这篇关于poj1177--Picture--扫描线的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1054188

相关文章

洛谷P5490扫描线

0是最小的数字,将一个线段看成一个区间,对于一个矩形,从下扫到上,入边为1,而出边为-1,意思是将这个区间上的所有点加1(区间修改).把线段表示为Line[i],其中记录了l,r,h,tag,左右端点,高度,入边还是出边(1或-1) 那么每次区间修改后不为0的区间它的值可能是1,2,3或者是其它数字,这不好统计,可以将它转化一下,0是不是表示没有被覆盖过的地方,我们只要统计0的个数然后用总长减去

Zxing扫描二维码精简(竖屏、拉伸处理、扫描框大小和扫描线移动、开灯)

自己在简版zxing的基础上美化了下,给大家分享下,直接扫描功能没问题。 就是从相册导入图片,解码一直不成功,导入图片解码 我引入了一个解码类  RGBLuminanceSource(百度网上二维码图片解码都是这个,我还把这个类编译了,导到core.jar包里面了), 好像是hity类型有问题,反正一直不成功。 有大神解决了,回复告诉我!谢谢! 分享 暂时没做效

Plus from Picture

Plus from Picture You have a given picture with size w×hw×h. Determine if the given picture has a single “+” shape or not. A “+” shape is described below: A “+” shape has one center nonempty cell. T

扫描线Sweep Line算法总结

扫描线算法,推荐还是用标准的模板去写,treemap只适合于求最大的overlap个数的题目,其余的不能用treemap来解,所以推荐还是用event的思想去+1, -1然后排序扫描的方法可以用来解所有的题型; Number of Airplanes in the Sky 思路:经典扫描线算法:把interval起飞和降落做为event,全部打散,按照时间排列,同时时间相等的,按照降落在前面,起

矩形面积并、矩形面积交、矩形周长并(线段树、扫描线总结)

转自:http://blog.csdn.net/lwt36/article/details/48908031 HDU 1542 [POJ 1151] Atlantis (矩形面积并) 题意: 求N<=100个矩形的面积并 分析: 离散化: 这些技巧都是老生常谈的了, 不然浮点数怎么建树, 离散化 x 坐标就可以了扫描线: 首先把矩形按 y 轴分成两条边, 上边和下边,

016_Save_the_picture_in_Matlab中保存图片

图片文件 Matlab核心功能包括出图,印刷质量的图片输出是Matlab核心竞争力之一,matplotlib疯狂追赶,但还是差距明显。出图的含义就是:打印或者导出图形窗体的内容,可供后续使用。在Matlab中,这个行为被定义为打印和保存。 相关的函数有三类: 导出 exportgraphics 导出绘图和图形内容(从R2020a开始)copygraphics 复制图形内容到剪贴板(从R202

【HDU1255】【线段树】【扫描线】【面积】

覆盖的面积 Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 4417    Accepted Submission(s): 2180 Problem Description 给定平面上若干矩形,求出被这些矩形覆

hdu 1162 Eddy's picture(基础最小生成树)

题目:         连接:点击打开链接 题意:         n个点,是每个点相互连通(直接间接),求最短距离。 思路:         prim()最小生成树。把点的距离存在map中。 代码: #include<iostream>#include<cstdio>#include<cmath>#include<cstring>using namespace std;

poj2482--Stars in Your Window(扫描线)

题目链接:点击打开链接 链接题目大意:给出n个星星的坐标,每个星星有一个亮度,给出一个矩形的长和宽,问矩形能包括的星星的最大亮度和(不包括边框)。 假设每个星星都是矩形的最左下点,那么每一个星星都可以得到一个矩形,(x,y)->(x,y,x+w,y+h),这个矩形的两条高边的值也就是星星的亮度k和-k,对于不同的矩形来说,如果高线出现重合部分,那么也就是说这两个星是可以出现在同一个矩形中的,扫

HDU 1828 POJ 1177 Picture(线段树+扫描线+离散化)

HDU题目地址:HDU 1828  POJ题目地址:POJ 1177 这题是求周长并,我用的方法可能有点麻烦。。是先求横着的线,再求竖着的线。每次只要求出每次的总区间覆盖长度,然后每次累加这次的总区间覆盖与上次的总区间覆盖长度的差的绝对值。因为只有长度发生变化时,才会产生一段新的周长。 待会再试试只扫描一次的方法。此博客有待更新。 代码如下: #include <iostream>#