CF30D题解

Miracle_1024 · 2023-05-21 07:11:38 · 题解

思路：

如题目描述，假设将所有点排序后，A 为最左点，C 为最右点，B 为起始点，D 为最后的 n + 1 点，E 为 A 到 C 中的任意一点。

枚举所有的 E 点 ( AE + ED + DE + EC + BC ) or ( BA + AE + ED + DE + EC ) 最短路的最优解必在其中。

代码:

#include<bits/stdc++.h>
#define int long long
using namespace std;
double x,y,xx[1000005];
int n,m,xxm;
double C(int z){return hypot(x-xx[z],y);}
double A(int l,int r){double z=xx[r]-xx[l]+min(C(l),C(r));return z;}
double B(int l,int r){double z;z=xx[r]-xx[l]+min(C(l)+abs(xxm-xx[r]),C(r)+abs(xxm-xx[l]));return z;}
signed main(){
    while(cin>>n>>m){
        for(int i=0;i<n;i++)cin>>xx[i];
        cin>>x>>y;
        xxm=xx[m-1];
        sort(xx,xx+n);
        double ans;
        if(m==n+1)ans=A(0,n-1);
        else {
            ans=B(0,n-1);
            for(int i=1;i<n;i++){
                double z;z=min(A(0,i-1)+B(i,n-1),A(i,n-1)+B(0,i-1));
                ans=ans<z?ans:z;
            }
    }
    cout<<setprecision(20)<<ans;
  }
}