Wall POJ - 1113 凸包模板-白红宇

Wall POJ - 1113 凸包模板

阅读量：4630 次

发布时间：2019-06-09

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

要求包围所有n个点并且距所有点距离大于L的多边形周长

这个多边形的周长可以通过凸包上的边做平移加上一个半径L的圆辅助转向得到

所以就是求凸包周长加上圆周长

主要是为了试试凸包的接口，实现用的是Graham，应该是单调栈吧？

//#include
     
        //#pragma comment(linker, "/STACK:1024000000,1024000000")   #include
      
         #include
       
          #include
        
           #include
         
            #include
          
            #include
           
             #include
            
              #include
              #include
              
                #include
               
                 using namespace std; const double pi=acos(-1.0); #define ll long long #define pb push_back const int maxn=1e3+56;const double eps=1e-6; int sgn(double x){ if(fabs(x)
                
                 0; } }; void norm(){ Point mi=p[0]; for(int i=1;i
                 
                  1 && sgn((convex.p[top-1]-convex.p[top-2])^ (p[i]-convex.p[top-2]))<=0)top--; convex.p[top++]=p[i]; } if(convex.n==2 && (convex.p[0]==convex.p[1]))convex.n--; } double getcircumference(){ double sum=0; for(int i=0;i

贴一个不用kb模板的轻量化板子：

//#include
     
        //#pragma comment(linker, "/STACK:1024000000,1024000000")   #include
      
         #include
       
          #include
        
           #include
         
            #include
          
            #include
           
             #include
            
              #include
              #include
              
                #include
               
                 using namespace std; const double pi=acos(-1.0); #define ll long long #define pb push_back#define sqr(a) ((a)*(a))#define dis(a,b) sqrt(sqr(a.x-b.x)+sqr(a.y-b.y))const int maxn=1e3+56;const int inf=0x3f3f3f3f;struct Point{ double x,y; int v,l; Point(double a=0,double b=0){x=a;y=b;} bool operator<(Point b)const{ return y
                
                 =(b.x-o.x)*(a.y-o.y);}double Graham(Point p[],int n,Point res[]){ //返回凸包周长 int top=1; sort(p,p+n); if(n==0)return 0;res[0]=p[0]; if(n==1)return 0;res[1]=p[1]; if(n==2)return dis(p[0],p[1])*2; res[2]=p[2]; for(int i=2;i
                 
                  =0;i--){ while(top!=len && (mult(p[i],res[top],res[top-1]))) top--; res[++top]=p[i]; } double c=dis(res[0],res[top-1]); for(int i=0;i
                  
                   min_val)continue; double c=Graham(tmp,res,ch); if(cut_len>=c){ if(cut_val