美文网首页
自己看的懂的凸包模板

自己看的懂的凸包模板

作者: Anxdada | 来源:发表于2017-03-10 16:10 被阅读0次

还是写了一个好懂点的凸包模板

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<iostream>
#define CLR(x) memset(x,0,sizeof(x))
#define ll long long int
#define PI acos(-1.0)
#define db double
using namespace std;

struct point
{
    int x,y;
}p[1005],s[1005];

/*叉积计算*/

int det(int x1,int y1,int x2,int y2)
{
    return x1*y2-x2*y1;
}

/* 求倒数第二个点和倒数第一个点,与倒数第一个点与当前点的叉乘*/
int cross(point o,point a,point b)
{
    return det(a.x-o.x,a.y-o.y,b.x-o.x,b.y-o.y);
}

/*求平方*/

db f(int x)
{
    return x*x*1.0;
}

/*水平排序*/

bool cmp(point a,point b)
{
    if(a.y==b.y)
        return a.x<b.x;
    return a.y<b.y;
}

db dis(point a,point b)
{
    return sqrt(f(a.x-b.x)+f(a.y-b.y));
}

int n,l;

int main()
{
    while(scanf("%d %d ",&n,&l)!=EOF)
    {
        for(int i=0;i<n;i++)
            scanf("%d %d",&p[i].x,&p[i].y);
        sort(p,p+n,cmp);
        int top=0;//正起扫一遍
        for(int i=0;i<n;i++)
        {
            while(top>=2 && cross(s[top-2],s[top-1],p[i])<0)//大于0,小于0完全看你向量的指向与谁相当于谁,
                                                             这个还是挺复杂的千万逻辑要清楚啊.
                top--;
            s[top++]=p[i];
        }
        int t=top+1;//反着再扫一遍
        for(int i=n-2;i>=0;i--)
        {
            while(top>=t && cross(s[top-2],s[top-1],p[i])<0)
                top--;
            s[top++]=p[i];
        }//凸包构建完成.
      int ans=0;
        for(int i=0;i<top-1;i++)
            ans+=dis(s[i],s[i+1]);//把凸包的所有边长求出来.
        printf("%d\n",ans);
    }
}

相关文章

  • 自己看的懂的凸包模板

    还是写了一个好懂点的凸包模板

  • 凸包

    向量的叉乘就是由该两个向量所组成的平行四边形的面积(x1y2-x2y1).这个凸包不是太懂.先留模板在此这个是水平...

  • Python3 趣味系列题8 ------ 凸包动态绘制

    本文介绍利用Graham Scan算法获得凸包(平面凸包),并动态展示凸包的形成过程。下面用比较通俗的语言,介绍下...

  • 凸包

    凸包最常用的凸包算法是Graham扫描法和Jarvis步进法Graham's Scan法这个算法是由数学大师葛立恒...

  • 凸包

    convexHull 实例

  • 凸包

    逼近多边形是轮廓的高度近似,但是有时候我们希望使用一个多边形的凸包来简化它。凸包跟逼近多边形很像,只不过它是物体最...

  • 点的凸包

    Description Convex Hull of a set of points, in 2D plane, ...

  • 提取平面点云的轮廓

    一. 基于凸包的凹点挖掘算法: 1. 提取点云的凸包 2. 计算凸包每条边的顶点的点密度(即该点 K 个临...

  • 3,4 仿射,凸,凸锥

    仿射组合凸组合凸锥组合组合后的所有点组成的称为仿射\凸\凸锥包

  • 算法复习-geometric algo

    convex hull 凸包-video25&video26 凸包算法剖析https://cyw3.github....

网友评论

      本文标题:自己看的懂的凸包模板

      本文链接:https://www.haomeiwen.com/subject/tafogttx.html