ACM几何入门---（二维凸包）以及入门题总结-白红宇的个人博客

发布日期：2021-05-07 01:27:29 浏览次数：22 分类：精选文章

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

最近学了下二维的凸包,打算去摸一摸这个专题!!!

这里的话，我觉得我会去把这个专题写完

板子

const int N=50005;struct Point{    double x,y;};Point stackk[N];	//凸包中所有点,下标从0....top开始 Point p[N];			//存入的所有点 Point MinA;int top;double dist(Point A,Point B){    return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));}//计算叉积 判断bc向量到ac向量 是否通过左转得到 >0左转 <0右转  =0共线 double cross(Point A,Point B,Point C)	{    return (B.x-A.x)*(C.y-A.y)-(B.y-A.y)*(C.x-A.x);} bool cmp(Point a,Point b)	//极角排序 {    double k=cross(MinA,a,b);    if(k>0) return 1;    if(k<0) return 0;    return dist(MinA,a)
   
    =1) --top;        stackk[++top]=p[i];    }    top++;}

第一题（凸包求周长）

**题意：**让你把树围起来，然后凸包搞一下，记得特判n = 1， n =2就行

AC代码

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 #include
                  
                   #define PI 3.14159265358979323846using namespace std;typedef long long int ll; typedef unsigned long long int ull;template
                   
                    inline T read(T&x){ x=0;int f=0;char ch=getchar(); while (ch<'0' || ch>'9') f|=(ch=='-'),ch=getchar(); while (ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar(); return x=f?-x:x;}const int N=50005;struct Point{ double x,y;};Point stackk[N]; //凸包中所有点,下标从0....top开始 Point p[N]; //存入的所有点 Point MinA;int top;double dist(Point A,Point B){ return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));}//计算叉积 判断bc向量到ac向量 是否通过左转得到 >0左转 <0右转 =0共线 double cross(Point A,Point B,Point C) { return (B.x-A.x)*(C.y-A.y)-(B.y-A.y)*(C.x-A.x);} bool cmp(Point a,Point b) //极角排序 { double k=cross(MinA,a,b); if(k>0) return 1; if(k<0) return 0; return dist(MinA,a)
                    
                     =1) --top; stackk[++top]=p[i]; } top++;}int n;// 求凸包的周长，然后考虑这个n ==1,2特例 void solve(){ for(int i = 0; i < n; i++){ cin>>p[i].x>>p[i].y; } Graham(n); double ans = 0.0; Point tmp = stackk[0]; for(int i = 1; i < top ;i++){ ans += dist(stackk[i-1],stackk[i]); } ans += dist(stackk[top-1],stackk[0]); if(n == 1){ ans = 0.0; } if(n == 2){ ans = dist(p[0],p[1]); } printf("%.2lf\n",ans);}int main(){ while(cin>>n){ if(n == 0) break; solve(); } return 0;}

第二题（凸包的周长 + 圆的周长）

题意： 最后就是让你求凸包的周长+圆的周长

需要注意的就是换行

AC代码

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 #include
                  
                   #define PI 3.14159265358979323846using namespace std;typedef long long int ll; typedef unsigned long long int ull;template
                   
                    inline T read(T&x){ x=0;int f=0;char ch=getchar(); while (ch<'0' || ch>'9') f|=(ch=='-'),ch=getchar(); while (ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar(); return x=f?-x:x;}const int N=50005;struct Point{ double x,y;};Point stackk[N]; //凸包中所有点,下标从0....top开始 Point p[N]; //存入的所有点 Point MinA;int top;double dist(Point A,Point B){ return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));}//计算叉积 判断bc向量到ac向量 是否通过左转得到 >0左转 <0右转 =0共线 double cross(Point A,Point B,Point C) { return (B.x-A.x)*(C.y-A.y)-(B.y-A.y)*(C.x-A.x);} bool cmp(Point a,Point b) //极角排序 { double k=cross(MinA,a,b); if(k>0) return 1; if(k<0) return 0; return dist(MinA,a)
                    
                     =1) --top; stackk[++top]=p[i]; } top++;}int n;double L;// 求凸包的周长+圆的周长 // 这个题目需要主要的就是最后一个数据不需要两个换行 void solve(){ cin>>n>>L; for(int i = 0; i < n; i++){ cin>>p[i].x>>p[i].y; } Graham(n); double ans = 0.0; Point tmp = stackk[0]; for(int i = 1; i < top ;i++){ ans += dist(stackk[i-1],stackk[i]); } ans += dist(stackk[top-1],stackk[0]); ans += 2 * PI * L; printf("%.0lf\n",ans);}int main(){ int t; cin>>t; while(t--){ solve(); if(t!=0){ printf("\n"); } } return 0;}

第三题（凸包+旋转卡壳求最大三角形面积）

**题意：**给你n个点，然后让你去求一个最大的三角形的面积

一个面积最大的话，一定是凸包上的点，具体… 说不明白，我也是看博客记住的，然后的话，就是+旋转卡壳… 都是板子

AC代码

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 #include
                  
                   #define PI 3.14159265358979323846using namespace std;typedef long long int ll; typedef unsigned long long int ull;template
                   
                    inline T read(T&x){ x=0;int f=0;char ch=getchar(); while (ch<'0' || ch>'9') f|=(ch=='-'),ch=getchar(); while (ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar(); return x=f?-x:x;}const int N=50005;struct Point{ double x,y;};Point stackk[N]; //凸包中所有点,下标从0....top开始 Point p[N]; //存入的所有点 Point MinA;int top;double dist(Point A,Point B){ return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));}//计算叉积 判断bc向量到ac向量 是否通过左转得到 >0左转 <0右转 =0共线 double cross(Point A,Point B,Point C) { return (B.x-A.x)*(C.y-A.y)-(B.y-A.y)*(C.x-A.x);} bool cmp(Point a,Point b) //极角排序 { double k=cross(MinA,a,b); if(k>0) return 1; if(k<0) return 0; return dist(MinA,a)
                    
                     =1) --top; stackk[++top]=p[i]; } top++;}int n;double L; // n个点组成的三角形面积最大 // 旋转卡壳 // 注意的就是输出的时候换成 .2f double rotating_calipers(int n) //n个点 { if(n <= 2){ return 0.00; } int j=1,k=0; double ans=0; for(int i=0;i

第四题（凸包+ 旋转卡壳求平面最远点对）

题意： 求平面最远点对的距离！！！直接凸包＋旋转卡壳

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 #include
                  
                   #define PI 3.14159265358979323846using namespace std;typedef long long int ll; typedef unsigned long long int ull;template
                   
                    inline T read(T&x){ x=0;int f=0;char ch=getchar(); while (ch<'0' || ch>'9') f|=(ch=='-'),ch=getchar(); while (ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar(); return x=f?-x:x;}typedef double elem_t;const int N=50005;struct Point{ elem_t x,y;};Point stackk[N]; //凸包中所有点,下标从0....top开始 Point p[N]; //存入的所有点 Point MinA;int top;double dist(Point A,Point B){ return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));}//计算叉积 判断bc向量到ac向量 是否通过左转得到 >0左转 <0右转 =0共线 elem_t cross(Point A,Point B,Point C) { return (B.x-A.x)*(C.y-A.y)-(B.y-A.y)*(C.x-A.x);} bool cmp(Point a,Point b) //极角排序 { double k=cross(MinA,a,b); if(k>0) return 1; if(k<0) return 0; return dist(MinA,a)
                    
                     =1) --top; stackk[++top]=p[i]; } top++;}//旋转卡壳求凸包的直径，平面最远的点对 // double也可以过elem_t dis2(Point a, Point b){ return (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y);}elem_t rotating_calipers_dist(int top){ int q=1; elem_t ans=0; stackk[top]=stackk[0]; for(int p=0; p<=top; p++) { while(cross(stackk[p+1],stackk[q],stackk[p])

第五题（凸包+ 求凸多边形的面积）

题意： 就是让你求下凸包，然后求凸边行的面积，可以用叉积，但是公式一定要对… 我就是这个area_sum（）一直理解错了…

AC代码

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 #include
                  
                   #define PI 3.14159265358979323846using namespace std;typedef long long int ll; typedef unsigned long long int ull;template
                   
                    inline T read(T&x){ x=0;int f=0;char ch=getchar(); while (ch<'0' || ch>'9') f|=(ch=='-'),ch=getchar(); while (ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar(); return x=f?-x:x;}typedef double elem_t;const int N=50005;struct Point{ elem_t x,y;};Point stackk[N]; //凸包中所有点,下标从0....top开始 Point p[N]; //存入的所有点 Point MinA;int top;double dist(Point A,Point B){ return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));}//计算叉积 判断bc向量到ac向量 是否通过左转得到 >0左转 <0右转 =0共线 elem_t cross(Point A,Point B,Point C) { return (B.x-A.x)*(C.y-A.y)-(B.y-A.y)*(C.x-A.x);} bool cmp(Point a,Point b) //极角排序 { double k=cross(MinA,a,b); if(k>0) return 1; if(k<0) return 0; return dist(MinA,a)
                    
                     =1) --top; // 这里判断稳定凸包不能有等号 也就是这个共线的情况必须算进去 stackk[++top]=p[i]; } top++;}double area_sum(Point sta[], int n){ // 求凸多边形面积 n是凸包大小 double ans = 0.0; int i = 0; for( i = 1; i < n-1; i++){ ans +=fabs(cross(sta[i],sta[i+1],sta[0])/2.0); } return ans;} int main(){ int n; int t; //scanf("%d",&t); while(scanf("%d",&n)!=EOF&&n) { for(int i=0;i

第六题（凸包+最小矩形覆盖）

题意： 裸的矩形覆盖，就是让你去求一个矩形，覆盖所有的点，然后这个矩阵的面积最小…

~~然后我真的没有动脑子和手去写…我觉得这个题型已经很死了。。。。所有我拿了别人写好的上了。。。。。~~

AC代码

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 #include
                  
                   #define PI 3.14159265358979323846using namespace std;const double eps = 1e-8;const int N = 50005;struct point{ double x, y; point operator - (point d) { point dd; dd.x = this -> x - d.x; dd.y = this -> y - d.y; return dd; } point operator + (point d) { point dd; dd.x = this -> x + d.x; dd.y = this -> y + d.y; return dd; }}p[N], ds[N];int n;int sign(double d) { return d < -eps ? -1 : (d > eps);}double dist(point d1, point d2){ return sqrt(pow(d1.x - d2.x, 2.0) + pow(d1.y - d2.y, 2.0)); }double dist2(point d1, point d2){ return pow(d1.x - d2.x, 2.0) + pow(d1.y - d2.y, 2.0); }bool cmp(point d1, point d2){ return d1.y < d2.y || (d1.y == d2.y && d1.x < d2.x); }//st1 --> ed1 叉乘 st2 --> ed2 的值double xmul(point st1, point ed1, point st2, point ed2){ return (ed1.x - st1.x) * (ed2.y - st2.y) - (ed1.y - st1.y) * (ed2.x - st2.x); } double dmul(point st1, point ed1, point st2, point ed2){ return (ed1.x - st1.x) * (ed2.x - st2.x) + (ed1.y - st1.y) * (ed2.y - st2.y); }//多边形类struct poly{ static const int N = 4005; //点数的最大值 point ps[N + 5]; //逆时针储存多边形的点,[0, pn - 1] int pn; // 点数 poly() { pn = 0; } void push(point tp) { // 加入一个点 ps[pn++] = tp; } int trim(int k) { //第k个位置 return (k + pn) % pn; } void clear() { pn = 0; } }; //返回含有n个点的点集ps的凸包poly graham(point* ps, int n){ sort(ps, ps + n, cmp); poly ans; if(n <= 2){ for(int i = 0; i < n; i++){ ans.push(ps[i]); } return ans; } ans.push(ps[0]); ans.push(ps[1]); point* tps = ans.ps; int top = -1; tps[++top] = ps[0]; tps[++top] = ps[1]; for(int i = 2; i < n; i++){ while(top > 0 && xmul(tps[top - 1], tps[top], tps[top - 1], ps[i]) <= 0) top--; tps[++top] = ps[i]; } int tmp = top; for(int i = n - 2; i >= 0; i--){ while(top > tmp && xmul(tps[top - 1], tps[top], tps[top - 1], ps[i]) <= 0) top--; tps[++top] = ps[i]; } ans.pn = top; return ans; }//求点p到st->ed的垂足，列参数方程 point getRoot(point p, point st, point ed){ point ans; double u=((ed.x-st.x)*(ed.x-st.x)+(ed.y-st.y)*(ed.y-st.y)); u = ((ed.x-st.x)*(ed.x-p.x)+(ed.y-st.y)*(ed.y-p.y))/u; ans.x = u*st.x+(1-u)*ed.x; ans.y = u*st.y+(1-u)*ed.y; return ans; } //next为直线(st,ed)上的点，返回next沿(st,ed)右手垂直方向延伸l之后的点 point change(point st, point ed, point next, double l){ point dd; dd.x = -(ed - st).y; dd.y = (ed - st).x; double len = sqrt(dd.x * dd.x + dd.y * dd.y); dd.x /= len, dd.y /= len; dd.x *= l, dd.y *= l; dd = dd + next; return dd; } //求含n个点的点集ps的最小面积矩形，并把结果放在ds(ds为一个长度是4的数组即可,ds中的点是逆时针的)中，并返回这个最小面积。double getMinAreaRect(point* ps, int n, point* ds){ int cn, i; double ans; point* con; poly tpoly = graham(ps, n); con = tpoly.ps; cn = tpoly.pn; if(cn <= 2){ ds[0] = con[0]; ds[1] = con[1]; ds[2] = con[1]; ds[3] = con[0]; ans=0; }else{ int l, r, u; double tmp, len; con[cn] = con[0]; ans = 1e40; l = i = 0; while(dmul(con[i], con[i+1], con[i], con[l]) >= dmul(con[i], con[i+1], con[i], con[(l-1+cn)%cn])){ l = (l-1+cn)%cn; } for(r=u=i = 0; i < cn; i++){ while(xmul(con[i], con[i+1], con[i], con[u]) <= xmul(con[i], con[i+1], con[i], con[(u+1)%cn])){ u = (u+1)%cn; } while(dmul(con[i], con[i+1], con[i], con[r]) <= dmul(con[i], con[i+1], con[i], con[(r+1)%cn])){ r = (r+1)%cn; } while(dmul(con[i], con[i+1], con[i], con[l]) >= dmul(con[i], con[i+1], con[i], con[(l+1)%cn])){ l = (l+1)%cn; } tmp = dmul(con[i], con[i+1], con[i], con[r]) - dmul(con[i], con[i+1], con[i], con[l]); tmp *= xmul(con[i], con[i+1], con[i], con[u]); tmp /= dist2(con[i], con[i+1]); len = xmul(con[i], con[i+1], con[i], con[u])/dist(con[i], con[i+1]); if(sign(tmp - ans) < 0){ ans = tmp; ds[0] = getRoot(con[l], con[i], con[i+1]); ds[1] = getRoot(con[r], con[i+1], con[i]); ds[2] = change(con[i], con[i+1], ds[1], len); ds[3] = change(con[i], con[i+1], ds[0], len); } } } return ans + eps;}// P 3187// double 求最小的面积 输出点 要求第一行为y坐标最小的顶点，//其后按逆时针输出顶点坐标.如果用相同y坐标，先输出最小x坐标的顶点void solve1(){ scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%lf%lf", &p[i].x, &p[i].y); printf("%.5f\n",getMinAreaRect(p, n, ds)+eps); for(int i = 0; i < 4; i++ ){ printf("%.5f %.5f\n",ds[i].x+eps,ds[i].y+eps); }}// HDU5251 输出矩形的面积为整数 int cas = 1;void solve2(){ scanf("%d", &n); n = n * 4; for (int i = 0; i < n; i++) scanf("%lf%lf", &p[i].x, &p[i].y); printf("Case #%d:\n%d\n", cas++, (int)(getMinAreaRect(p, n, ds) + 0.5));}int main() { int t; t = 1; scanf("%d", &t); while (t--) { //solve2(); solve1(); } return 0;}

持续更新中…

上一篇：ACM矩阵---题目总结+矩阵构造

下一篇：Acm解题技巧---Hash字符串

发表评论

关于作者

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

-- 愿君每日到此一游！

最近学了下二维的凸包,打算去摸一摸这个专题!!!

板子

第一题（凸包求周长）

AC代码

第二题（凸包的周长 + 圆的周长）

AC代码

第三题（凸包+旋转卡壳求最大三角形面积）

AC代码

第四题（凸包+ 旋转卡壳求平面最远点对）

第五题（凸包+ 求凸多边形的面积）

AC代码

第六题（凸包+最小矩形覆盖）

AC代码

持续更新中…

发表评论

最新留言

关于作者

推荐文章