Loading...

凸包学习笔记

check评论:0 条 remove_red_eye浏览量:366 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2018-12-29

qwq我太菜啦,才学凸包

感谢yyb dalao的图

首先啥是凸包?

这外面一圈就是个凸包qwq

然后我们怎么来求凸包呐?

我们先找出最左下角的那个点

然后将其他的点按极角排序,也就是将其他点和这个最左下角点所在的直线按与$x$轴夹角$tan$值来排序

然后我们先将$1,2$点推入凸包栈,并与下一个比较,如果当前点在之前凸包的一侧(不形成凹多边形)就将其加入,但如果上一个点没有当前点那么向外侧,就将其弹出栈

比如这幅图中,$2$在$1,3$连线的内侧,形成了凹多边形,故弹出

然后依次这样操作,就能找到凸包了

例题:洛谷P2742二维凸包

我们直接求出凸包,然后求出两两点间距离之和即可

#include <bits/stdc++.h>
using namespace std;
struct node
{
    double x,y;
}p[100010],s[100010];
int top,n;
bool cmp(node a,node b)
{
    double A=atan2((a.y-p[1].y),(a.x-p[1].x));
    double B=atan2((b.y-p[1].y),(b.x-p[1].x));
    if(A!=B)
    {
        return A<B;
    }
    else
    {
        return a.x<b.x;
    }
}
double cross(node a,node b,node c)
{
    return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
void get()
{
    p[0]=(node){0x3f3f3f3f,0x3f3f3f3f};
    int k;
    for(int i=1;i<=n;i++)
    {
        if(p[0].y>p[i].y||(p[0].y==p[i].y&&p[0].x>p[i].x))
        {
            p[0]=p[i];
            k=i;
        }
    }
    swap(p[k],p[1]);
    sort(p+2,p+n+1,cmp);
    s[0]=p[1],s[1]=p[2],top=1;
    for(int i=3;i<=n;)
    {
        if(top&&cross(s[top-1],p[i],s[top])>=0)
        {
            top--;
        }
        else
        {
            s[++top]=p[i++];
        }
    }
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        scanf("%lf%lf",&p[i].x,&p[i].y);
    }
    get();
    double ans=0.0;
    for(int i=1;i<=top;i++)
    {
        ans+=sqrt((s[i].x-s[i-1].x)*(s[i].x-s[i-1].x)+(s[i].y-s[i-1].y)*(s[i].y-s[i-1].y));
    }
    ans+=sqrt((s[top].x-s[0].x)*(s[top].x-s[0].x)+(s[top].y-s[0].y)*(s[top].y-s[0].y));
    printf("%.2lf",ans);
}

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名