首页 > 代码库 > hdu 1255 覆盖的面积 线段树扫描线求重叠面积
hdu 1255 覆盖的面积 线段树扫描线求重叠面积
稀里糊涂打完了没想到1A了,心情还是很舒畅的,c和c++的四舍五入还是四舍六入遇积进位遇偶舍,我感觉很混乱啊,这道题我输出的答案是7.62,也就是遇偶舍了,可是我就手动处理一下进位问题,发现0.005 系统自动进位0.01了,尼玛啊,我一下子就混乱了,不是遇偶舍么,0也是偶数啊,怎么就进位了呢。最后我就不手动处理进位问题了,直接0.2lf%,虽然我输出的结果是7.62,但是提交也过了
这道题和poj1151,hdu1542差不多,扫描线详细讲解http://blog.csdn.net/youngyangyang04/article/details/7787693但是这个是求重叠的面积,需要处理的细节还是挺多的,我有单独写了一个求和函数sum,因为放在insert里面求和会遇到很多问题啊,还有就是离散花的时候也会遇到各种问题,总之要细心啊
#include<iostream> #include<stdio.h> #include<algorithm> using namespace std; #define N 3000 struct Node{ double y1,y2,x;//x 轴上对应两个y直 int flag;//标记入度还是出度,入度为1,出度为-1 }node[N]; bool cmp(Node a,Node b){ return a.x-b.x<0.0000000001; } struct node{ int l,r,s;//s表示度的数,也就是有几条边覆盖 double ml,mr,len;//len表示度》=2的边的长度 }a[N*3]; double y[N]; void build(int left,int right,int i){ a[i].l=left; a[i].r=right; a[i].ml=y[left];//离散化的 a[i].mr=y[right]; a[i].s=0; if((a[i].r-a[i].l)==1) return ; int mid=(a[i].l+a[i].r)>>1; build(a[i].l,mid,i*2); build(mid,a[i].r,i*2+1); } void insert(Node b,int i){ if(a[i].ml==b.y1&&a[i].mr==b.y2){//如果找到这条边就加上这条边的度<span style="font-family: Arial, Helvetica, sans-serif;">b.flag,度表示有几条边覆盖</span> a[i].s+=b.flag; return ; } if(a[i].s!=0){//向下拓展,这一步很重要 a[i*2].s+=a[i].s; a[i*2+1].s+=a[i].s; a[i].s=0; } int mid=(a[i].r+a[i].l)>>1; if(b.y2<=y[mid]) insert(b,i*2); else if(b.y1>=y[mid]) insert(b,i*2+1); else{ Node temp=b; temp.y2=y[mid]; insert(temp,i*2); temp=b; temp.y1=y[mid]; insert(temp,i*2+1); } } void sum(int i){ if(a[i].r-a[i].l==1){ if(a[i].s>=2) a[i].len=a[i].mr-a[i].ml; else a[i].len=0; return; } if(a[i].s!=0){ a[i*2].s+=a[i].s; a[i*2+1].s+=a[i].s; a[i].s=0; } sum(i*2); sum(i*2+1); a[i].len=a[i*2].len+a[i*2+1].len;//求出該边度>=2的长度 } int main(){ int t,n; double x1,x2,y1,y2; scanf("%d",&t); while(t--){ int cou=1; scanf("%d",&n); while(n--){ scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2); node[cou].x=x1; node[cou].y1=y1; node[cou].y2=y2; node[cou].flag=1; y[cou++]=y1; node[cou].x=x2; node[cou].y1=y1; node[cou].y2=y2; node[cou].flag=-1; y[cou++]=y2; } sort(y+1,y+cou); sort(node+1,node+cou,cmp); build(1,cou-1,1); double ans=0; insert(node[1],1); sum(1); for(int i=2;i<cou;i++){ ans+=a[1].len*(node[i].x-node[i-1].x); insert(node[i],1); sum(1); } printf("%.2lf\n",ans); } }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。