题意：给n个点，其中n-1个共线，指定一个起点，每次可从一个点沿直线移动至另一个点，点可重复访问，问访问过所有点至少一次的最短路径。
首先我们肯定要找出不共线的那个点。按x坐标将n个点排序，计算出所有相邻两点的斜率，只要点数大于等于四，那么和其它不同的两个斜率之间的点就是不共线的点。（仅有三个点的情况直接算一下就好。）为了方便起见，我们可以重新排个序，将不共线点放到最后，1到n-1为有序的共线点。
显然，如果没有不共线点，那么我们肯定始终沿直线移动，故不共线点仅会被访问一次。以及，进行多次折回显然无意义，在除端点外的所有位置不应进行多于一次折回。
故对于起点不是不共线点的情况，我们相当于将共线点分成连续的两端——经过不共线点之前访问和之后访问。首先枚举K≤i＜n-1，ans1 = min( dis(K,i) + dis(i,1) + dis(1,n) + dis(n,i+1) + dis(i+1,n-1), dis(k,1) + dis(1,i) + dis(i,n) + dis(n,i+1) + dis(i+1,n-1) ); 同理1<i≤K， ans2 = min( dis(K,i) + dis(i,n-1) + dis(n-1,n) + dis(n,i-1) + dis(i-1,1), dis(k,n-1) + dis(n-1,i) + dis(i,n) + dis(n,i-1) + dis(i-1,1) )。最终答案是min(ans1, ans2)，再单独计算一下i=1或n-1的情况，一起取个最小值。
如果起点就是不共线点，那么很简单，答案就是dis(1,n−1) + min(dis(1, n), dis(n−1, n)).
一开始自己写的时候没考虑全情况……
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define ll long long
using namespace std;
const int N=200010;
const double eps=1e-10;
struct Point{
int x,y,id,rnk;
}p1[N];
int n,m,s,p;
bool ok[N];
double ans,tot;
bool cmp(Point i,Point j){
if(i.x!=j.x)return i.x<j.x;
return i.y<j.y;
}
bool cmp1(Point i,Point j){
return i.rnk<j.rnk;
}
inline bool check(Point i,Point j,Point k){
return 1ll*(j.x-i.x)*(k.y-j.y)==1ll*(k.x-j.x)*(j.y-i.y);
}
inline double dis(int i,int j){
return sqrt(1.0*(p1[i].x-p1[j].x)*(p1[i].x-p1[j].x)+1.0*(p1[i].y-p1[j].y)*(p1[i].y-p1[j].y));
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)scanf("%d%d",&p1[i].x,&p1[i].y),p1[i].id=i;
if(n==3){
double tmp[3];
ans=dis(1,2)+dis(2,3)+dis(3,1);
for(int i=1,j=0;i<=3;++i){
if(i!=m)tmp[++j]=dis(i,m);
}
ans-=max(tmp[1],tmp[2]);
printf("%lf\n",ans);
return 0;
}
sort(p1+1,p1+n+1,cmp);
for(int i=1;i<=n;++i)p1[i].rnk=i;
p=0;
for(int i=2;i<n;++i)
ok[i]=check(p1[i-1],p1[i],p1[i+1]);
for(int i=2;i<n;++i)
if(!ok[i-1]&&!ok[i]&&!ok[i+1])p=i;
if(!p&&!ok[2])p=1;
else if(!p) p=n;
p1[p].rnk=n+1;
sort(p1+1,p1+n+1,cmp1);
for(int i=1;i<=n;++i)if(p1[i].id==m)s=i;
if(s!=n){
ans=min(dis(s,n-1)+dis(n-1,1)+dis(1,n),dis(s,1)+dis(1,n-1)+dis(n-1,n));
for(int i=s;i<n-1;++i){
tot=min(dis(s,i)+dis(i,1)+dis(1,n)+dis(n,i+1)+dis(i+1,n-1),dis(s,1)+dis(1,i)+dis(i,n)+dis(n,i+1)+dis(i+1,n-1));
ans=min(ans,tot);
}
for(int i=2;i<=s;++i){
tot=min(dis(s,i)+dis(n-1,i)+dis(n-1,n)+dis(n,i-1)+dis(i-1,1),dis(s,n-1)+dis(n-1,i)+dis(i,n)+dis(n,i-1)+dis(i-1,1));
ans=min(ans,tot);
}
}else ans=dis(1,n-1)+min(dis(1,n),dis(n-1,n));
printf("%lf\n",ans);
return 0;
}