求助Andrew凸包
查看原帖
求助Andrew凸包
763542
Furina_Hate_Comma楼主2023/5/19 12:49
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
class Vector{
    public:
        double x,y;
        Vector(double x1,double y1){x=x1,y=y1;}
        double dot(Vector a){return a.x*x+a.y*y;}
        double cross(Vector a){return a.y*x-a.x*y;}
};
class point{
    public:
        double x,y;
        Vector operator-(point &b){return Vector(x-b.x,y-b.y);}
        double dis(point a){return sqrt((a.x-x)*(a.x-x)+(a.y-y)*(a.y-y));}
};
double super_cross(point a,point b,point c){
    Vector x=a-b,y=c-b;
    return x.cross(y);
}
class mystack{
    public:
        point st[N];
        int top;
        mystack(){top=0;}
        void push(point p){st[++top]=p;}
        void pop(){top--;}
};
bool cmp(point a,point b){
    if(a.x==b.x)
        return a.y<b.y;
    return a.x<a.y;
}
class object{
    public:
        int n;
        point p[N];
        point tb[N];
        int andrew(int n){
            sort(p,p+n+1,cmp);
            mystack st;
            for(int i=1;i<=n;i++){
                while(st.top>1&&super_cross(st.st[st.top-1],st.st[st.top],p[i])<=0)
                    st.pop();
                st.push(p[i]);
            }
            st.push(p[n]);
            for(int i=n-1;i>=1;i--){
                while(st.top>1&&super_cross(st.st[st.top-1],st.st[st.top],p[i])<=0)
                    st.pop();
                st.push(p[i]);
            }
            for(int i=1;i<=st.top;i++)
                tb[i]=st.st[i];
            return st.top;
        }
};
object a;
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a.p[i].x>>a.p[i].y;
    double k=a.andrew(n),ans=0;
    for(int i=2;i<=k;i++)
        ans+=a.tb[i].dis(a.tb[i-1]);
    ans+=a.tb[1].dis(a.tb[n]);
    cout<<ans;
}
2023/5/19 12:49
加载中...