UVA LA3218 找边界，PSLG-白红宇的个人博客

UVA LA3218 找边界，PSLG

发布日期：2021-10-08 15:48:55 浏览次数：14 分类：技术文章

本文共 2202 字，大约阅读时间需要 7 分钟。

分析：

本题是求PSLG得外轮廓，需要借助与前面所说的“类似卷包裹”的算法。具体来说，首先找到x坐标最小的点（如果有多个，找y坐标最小的点），然后开始“卷包裹”。

首先找到初始边。

然后每次都执行如下操作。

首先看看当前线段是否和其他线段相交（根据题意，一定是规范相交）,如果不想交，说明可以直接走到当前线段的终点，否则走到最近的交点就得停下来，接下来转弯

并继续前进。转弯时如果有多条路可以走，选择那条右转的最厉害的线段。转回原点以后，整个过程结束。

这题代码比较繁琐，不容易懂，看了大牛的代码看了好久也没完全理解，

lower_bound()函数讲解：

函数lower_bound()在first和last中的前闭后开区间进行二分查找，返回大于或等于val的第一个元素位置。如果所有元素都小于val，则返回last的位置

举例如下：

一个数组number序列为：4,10,11,30,69,70,96,100.设要插入数字3,9,111.pos为要插入的位置的下标

则

pos = lower_bound( number, number + 8, 3) - number，pos = 0.即number数组的下标为0的位置。

pos = lower_bound( number, number + 8, 9) - number， pos = 1，即number数组的下标为1的位置（即10所在的位置）。

pos = lower_bound( number, number + 8, 111) - number， pos = 8，即number数组的下标为8的位置（但下标上限为7，所以返回最后一个元素的下一个元素）。

所以，要记住：函数lower_bound()在first和last中的前闭后开区间进行二分查找，返回大于或等于val的第一个元素位置。如果所有元素都小于val，则返回last的位置，且last的位置是越界的！！~

返回查找元素的第一个可安插位置，也就是“元素值>=查找值”的第一个元素的位置

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            #include
             
              #include
              
               #include
               
                using namespace std;const double eps=1e-6;int dcmp(double x){ if(fabs(x)
                
                 0?1:-1; //return fabs(x) < eps ? 0 : (x > 0 ? 1 : -1);}struct point{ double x; double y; point(){} point(double x,double y):x(x),y(y){} void in() { cin>>x>>y; } void out() { cout<
                 
                  <<' '<
                  
                   <
                   
                    0;}point getintersection(line a,line b){ point u=a.p-b.p; double t=cross(b.v,u)/cross(a.v,b.v); return a.p+a.v*t;}bool sgementproperintersection(point a1,point a2,point b1,point b2){ double c1=cross(a2-a1,b1-a1),c2=cross(a2-a1,b2-a1), c3=cross(b2-b1,a1-b1),c4=cross(b2-b1,a2-b1); return dcmp(c1)*dcmp(c2)<0&&dcmp(c3)*dcmp(c4)<0;}bool onsegment(point p,point a1,point a2){ return dcmp(cross(a1-p,a2-p))==0&&dcmp(dot(a1-p,a2-p))<0;}typedef vector
                    
                      Polygon;double PolygonArea(Polygon poly){ double area=0; int n=poly.size(); for(int i=1;i
                     
                       edges; vector
                      
                        G[maxn]; int vis[maxn*2]; int left[maxn*2]; int prev[maxn*2]; vector
                       
                         faces; double area[maxn]; void init(int n) { this->n=n; for(int i=0;i
                        
                         edges[G[u][j]].ang) swap(G[u][i],G[u][j]); } for(int i=0;i
                         
                           dist[maxp]; c=n; for(int i=0;i
                          
                           >n&&n) { for(int i=0;i
                           
                            >P[i].x>>P[i].y; build_graph(); Polygon poly; for(int i=0;i

就暂时抄写了一遍，留着慢慢理解吧。

转载地址：https://blog.csdn.net/ONE_PIECE_HMH/article/details/45727507 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：PSLG,直线切割凸多边形，和判断圆与多边形相交

下一篇：UVA LA 2797 PSLG 线段闭合圈神奇的精度问题

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章