题意分析
首先确定起点 $k$ 是简单的。记 $a_1,a_2,\cdots,a_n$ 为原来的 $n$ 个点。
可以统一将 $a_1,a_2,\cdots,a_k$ 与 $a_{k+1},a_{k+2},\cdots,a_n$ 交换在序列中的位置，这样便于处理。交换后仍然为凸多边形。
考虑原问题等价于对新的 $a_1,a_2,\cdots,a_{n-1}$ 进行全排列，求最小答案。因此考虑 DP。
设 $\textit{dp}{l,r,0},\textit{dp}{l,r,1}$ 分别表示走完 $a_l\sim a_r$，最终停在 $a_l$ 或者 $a_r$ 的最小代价。
记 $\operatorname{dist}(i,j)$ 表示 $a_i,a_j$ 之间的距离，则有：
\[\begin{aligned} \textit{dp}_{l,r,0}&=\min(\textit{dp}_{l+1,r,0}+\operatorname{dist}(l+1,l),\textit{dp}_{l+1,r,1}+\operatorname{dist}(r,l))\\ \textit{dp}_{l,r,1}&=\min(\textit{dp}_{l,r-1,0}+\operatorname{dist}(l,r),\textit{dp}_{l,r-1,1}+\operatorname{dist}(r-1,r))\\ \end{aligned}\]因为路径不会交叉。路径交叉一定不优，可以将其转化为不交叉的情况。
输出路径，记录每一个 $\textit{dp}{l,r,i}$ 的前驱状态 $\textit{pre}{l,r,i}$ 即可，注意到其实只和 $i\in\set{0,1}$ 有关，因此可以只记录前驱状态的 $i$。
AC 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
constexpr const double eps=1e-12,inf=1e17;
constexpr const int N=1e3;
struct node{
double x,y;
int id;
}a[N+1],tmp[N+1];
int n,k;
double dp[N+1][N+1][2];
int pre[N+1][N+1][2];
double dist(int i,int j){
return sqrt((a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y));
}
bool equal(double a,double b){
return abs(a-b)<=eps;
}
void print(int l,int r,bool op){
if(l==r){
cout<<a[l].id<<' ';
return;
}
switch(op){
case 0:
cout<<a[l].id<<' ';
print(l+1,r,pre[l][r][op]);
break;
case 1:
cout<<a[r].id<<' ';
print(l,r-1,pre[l][r][op]);
break;
}
}
int main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i].x>>a[i].y;
a[i].id=i;
tmp[i]=a[i];
}
k=1;
for(int i=2;i<=n;i++){
if(a[i].y>a[k].y){
k=i;
}
}
for(int i=1;i<=k;i++){
a[i+n-k]=tmp[i];
}
for(int i=k+1;i<=n;i++){
a[i-k]=tmp[i];
}
for(int len=2;len<=n;len++){
for(int l=1,r=len;r<=n;l++,r++){
double x=dp[l+1][r][0]+dist(l+1,l);
double y=dp[l+1][r][1]+dist(r,l);
if(x<y){
dp[l][r][0]=x;
pre[l][r][0]=0;
}else{
dp[l][r][0]=y;
pre[l][r][0]=1;
}
x=dp[l][r-1][0]+dist(l,r);
y=dp[l][r-1][1]+dist(r-1,r);
if(x<y){
dp[l][r][1]=x;
pre[l][r][1]=0;
}else{
dp[l][r][1]=y;
pre[l][r][1]=1;
}
}
}
cout<<a[n].id<<' ';
if(dp[1][n-1][0]+dist(1,n)<dp[1][n-1][1]+dist(n-1,n)){
print(1,n-1,0);
}else{
print(1,n-1,1);
}
cout.flush();
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
