【题目大意】
有n个点在x轴上,第n+1个点可能在任意的地方,问从k号点出发最短遍历需要走多远
【输入】
第一行两个数字n、k,意义如题目所示
接下来一行n+1个数字,分别表示n+1个点的x坐标
之后一行一个数字表示第n+1号点的y坐标
首先考虑k=n+1的时候
根据三角形不等式,肯定是走到一个x轴上最左或最右的点,然后直着走
当起点在x轴上的时候
有两种情况
一种是走到一头然后再调头走到另外一头然后走向n+1号点
另外一种是从某个点i分开,
然后变成这个样子
1----i-----i+1----k-----n
这种先走向i+1或者n,然后再调头,走向n+1,再走向1或者i之后走向i或者1
或者
1----k-----i-----i+1----n
这种类似……
#include <cstdio> #include <iostream> #include <algorithm> #include <cmath> using namespace std; int n,k,i,j,x[100001],s[100001],dl[100001],a,b; double ans; double dis(double x1,double y1,double x2,double y2) { return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)); } bool cmp(int a,int b) { return x[a]<x[b]; } double quicku(double s,double e) { return e-s+min(dis(a,b,s,0),dis(a,b,e,0)); } double quickd(double s,double m,double e) { return min( m+e-2*s+dis(a,b,e,0), 2*e-s-m+dis(a,b,s,0)); } int main() { scanf("%d%d",&n,&k); for (i=1;i<=n;i++) scanf("%d",&x[i]); scanf("%d%d",&a,&b); for (i=1;i<=n;i++) dl[i]=i; sort(dl+1,dl+1+n,cmp); if (k==n+1) { printf("%.10f\n",x[dl[n]]-x[dl[1]]+min(dis(a,b,x[dl[n]],0),dis(a,b,x[dl[1]],0))); return 0; } for (i=1;i<=n;i++) if (dl[i]==k) { k=i; break; } for (i=1;i<=n;i++) s[i]=x[dl[i]]; ans=(s[n]-s[k])*2+s[k]-s[1]+dis(a,b,s[1],0); ans=min(ans,s[n]-s[1]+s[k]-s[1]+dis(a,b,s[n],0)); for (i=2;i<=k;i++) ans=min(ans,quicku(s[1],s[i-1])+quickd(s[i],s[k],s[n])); for (i=k;i<n;i++) ans=min(ans,quickd(s[1],s[k],s[i])+quicku(s[i+1],s[n])); printf("%.10f\n",ans); cin.get(); cin.get(); return 0; }