27分求调
查看原帖
27分求调
672237
qinshi0308楼主2024/7/19 11:42

27分,只A了前三个点。

# include <bits/stdc++.h>
using namespace std;
pair<double,double> arr[100010],O;
pair<int,pair<double,double> > brr[100010];
int crr[100010];
inline double dis(pair<double,double> a,pair<double,double> b=O){
    double x=a.first-b.first,y=a.second-b.second;
    return sqrt(x*x+y*y);
}
inline bool UoD(pair<double,double> x){
    return x.second>0||(!x.second&&x.first>0);
}
inline double check(pair<int,int> a,pair<int,int> b,pair<int,int> c){
    return ((a.first-c.first)*(b.second-c.second))-((b.first-c.first)*(a.second-c.second));
}
inline bool cmp(pair<int,pair<double,double> > a,pair<int,pair<double,double> > b){
    if(a.second.first==0&&a.second.second==0){
        return 1;
    }
    if(b.second.first==0&&b.second.second==0){
        return 0;
    }
    int va=UoD(a.second),vb=UoD(b.second);
    if(va!=vb){
        return va>vb;
    }
    double v=check(a.second,b.second,make_pair(0,0));
    if(v==0){
        return dis(a.second)<dis(b.second);
    }
    return v>0;
}
int main(){
    int n;
    cin>>n;
    double minx=1e6,miny=1e6;
    int mini;
    for(int i=0;i<n;i++){
        cin>>arr[i].first>>arr[i].second;
        if(arr[i].first<minx){
            minx=arr[i].first;
            miny=arr[i].second;
            mini=i;
        }else if(arr[i].first==minx&&arr[i].second<miny){
            miny=arr[i].second;
            mini=i;
        }
    }
    O=arr[mini];
    for(int i=0,j=0;i<n;i++){
        if(i!=mini){
            brr[j].first=i;
            brr[j++].second=arr[i];
        }
    }
    sort(brr,brr+n-1,cmp);
    int m=1;
    crr[0]=mini;
    for(int i=0;i<n-1;i++){
        while(m>2&&check(arr[crr[m-1]],brr[i].second,arr[crr[m-2]])<=0){
            m--;
        }
        crr[m++]=brr[i].first;
    }
    double ans=0;
    for(int i=1;i<m;i++){
        ans+=dis(arr[crr[i]],arr[crr[i-1]]);
    }
    ans+=dis(arr[crr[m-1]],arr[crr[0]]);
    cout<<fixed<<setprecision(2)<<ans<<endl;
    // for(int i=0;i<m;i++){
    //     cout<<crr[i]<<" ";
    // }
    return 0;
}
2024/7/19 11:42
加载中...