凸包问题-graham-scan算法c++实现

好的，以下是Graham-Scan算法的C++实现代码：

#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
using namespace std;

struct point{
    double x,y;
};

point p[100005],s[100005];

inline double cross(point a,point b,point c){
    return (a.x-c.x)*(b.y-c.y)-(b.x-c.x)*(a.y-c.y);
}

inline double dis(point a,point b){
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

inline bool cmp(point a,point b){
    double k=cross(a,b,p[1]);
    if(k>0||(k==0&&dis(a,p[1])<dis(b,p[1]))) return 1;
    else return 0;
}

int main(){
    int n,top=0;
    cin>>n;
    for(int i=1;i<=n;++i) cin>>p[i].x>>p[i].y;
    for(int i=2;i<=n;++i)
        if(p[i].y<p[1].y||(p[i].y==p[1].y&&p[i].x<p[1].x)) swap(p[i],p[1]);
    sort(p+2,p+n+1,cmp);
    s[++top]=p[1],s[++top]=p[2];
    for(int i=3;i<=n;++i){
        while(top>1&&cross(p[i],s[top],s[top-1])>=0) top--;
        s[++top]=p[i];
    }
    double ans=0;
    s[top+1]=s[1];
    for(int i=1;i<=top;++i) ans+=dis(s[i],s[i+1]);
    printf("%.2lf",ans);
    return 0;
}

其中，结构体`point`表示一个点，`cross()`函数计算两个向量的叉积，`dis()`函数计算两个点之间的距离。在`cmp()`函数中，比较两个点的大小，用于在排序时确定极角大小。在主函数中，先输入点的数量和坐标，然后找到y坐标最小的点p[1]，按极角排序，将凸包上的点存入栈s中，最后计算凸包周长。