WA在#2 菜鸡求调
查看原帖
WA在#2 菜鸡求调
507534
YBaggio楼主2023/3/5 08:35
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cmath>
using namespace std;
const int maxn=100005;
int n,b[maxn],top,S,T;
long double ans,res;
pair<int,int>a[maxn],s,t;
long double dist(int i,int j){
    return sqrt(1.0*(a[i].first-a[j].first)*(a[i].first-a[j].first)+1.0*(a[i].second-a[j].second)*(a[i].second-a[j].second));
}
pair<int,int> operator-(pair<int,int>x,pair<int,int>y){
    return {x.first-y.first,x.second-y.second};
}
long double operator*(pair<int,int>x,pair<int,int>y){
    return x.first*y.second-x.second*y.first;
}
bool check(int i,int j,int k){
    pair<int,int>x=a[j]-a[i],y=a[k]-a[j];
    return x*y<0;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i].first>>a[i].second;
    cin>>s.first>>s.second>>t.first>>t.second;
    a[0]=s;a[++n]=t;
    sort(a,a+n+1);
    b[++top]=0;b[++top]=1;
    for(int i=2;i<=n;i++){
        while(top>2&&check(b[top-1],b[top],i)){
            top--;
        }
        b[++top]=i;
    }bool flag=false;
    int fflag=0;
    for(int i=1;i<=top;i++){
        if(a[b[i]]==s)S=b[i],fflag++;
        if(a[b[i]]==t)T=b[i],fflag++;
    }
    if(fflag!=2)ans=1e10;
    else for(int i=1;i<top;i++){
        if(S==b[i])flag=true;
        if(T==b[i])flag=false;
        if(flag)ans+=dist(b[i],b[i+1]);
    }
    top=0;fflag=0;
    b[++top]=n;b[++top]=n-1;
    for(int i=n-2;i>=1;i--){
        while(top>2&&check(b[top-1],b[top],i)){
            top--;
        }
        b[++top]=i;
    }
    flag=false;
    for(int i=1;i<=top;i++){
        if(a[b[i]]==s)S=b[i],fflag++;
        if(a[b[i]]==t)T=b[i],fflag++;
    }
    if(fflag!=2)res=1e10;
    else for(int i=1;i<top;i++){
        if(b[i]==S)flag=true;
        if(b[i]==T)flag=false;
        if(flag)res+=dist(b[i],b[i+1]);
    }
    cout<<fixed<<setprecision(11)<<min(ans,res)<<endl;
    return 0;
}
2023/3/5 08:35
加载中...