RT，我的做法就是类似关路灯的DP，g记录上一个状态的左端点，h右端点，p记录0/1，这三个数组就是输出的时候用的，记录现在的状态从哪个状态转移过来（这样似乎不必要，但我觉得这样好想）。

球球各路大佬帮帮蒟蒻QWQ。

#include <bits/stdc++.h>
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define mp make_pair
#define fir first
#define sec second
#define ll long long
#define ld long double
using namespace std;
const int N=1e3+5;
const int mod=998244353;
const double inf=1e9;
const ll  INF=0x3f3f3f3f3f3f3f3f;

struct node {
	double x,y;
	int id;
	bool operator < (const node &t) {
		return x<t.x;
	}
}a[N];
int n,g[N][N][2],h[N][N][2],p[N][N][2];
double f[N][N][2];

double cal(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));
}
void out(int l, int r, int k) {
	if(l==r)
	{
		printf("%d ", a[l].id);
		return;
	}
	// cout<<l<<' '<<r<<' '<<k<<": "<<g[l][r][k]<<" "<<h[l][r][k]<<' '<<p[l][r][k]<<endl;
	out(g[l][r][k],h[l][r][k],p[l][r][k]);
	if(g[l][r][k]>l) printf("%d ", a[l].id);
	else printf("%d ", a[r].id);
}
int main()
{
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    //ios::sync_with_stdio(false);
    scanf("%d", &n);
    for(int i=1; i<=n; i++) scanf("%lf%lf", &a[i].x, &a[i].y),a[i].id=i;
    sort(a+1,a+n+1);
	
	for(int l=1; l<=n; l++)
		for(int r=1; r<=n; r++)
			f[l][r][0]=f[l][r][1]=inf;
	int st=0;
	for(int i=1; i<=n; i++)
		if(a[i].y>a[st].y) st=i;
	f[st][st][0]=f[st][st][1]=0;
	// for(int i=1; i<=n; i++) f[i][i][0]=f[i][i][1]=0;
	for(int len=2; len<=n; len++)
	{
		for(int l=1; l+len-1<=n; l++)
		{
			int r=l+len-1;

			if(f[l][r-1][1]+cal(r-1,r)<f[l][r][1])
			{
				f[l][r][1]=f[l][r-1][1]+cal(r-1,r);
				g[l][r][1]=l;
				h[l][r][1]=r-1;
				p[l][r][1]=1;
			}
			if(f[l][r-1][0]+cal(l,r)<f[l][r][1])
			{
				f[l][r][1]=f[l][r-1][0]+cal(l,r);
				g[l][r][1]=l;
				h[l][r][1]=r-1;
				p[l][r][1]=0;
			}
			if(f[l+1][r][0]+cal(l,l+1)<f[l][r][0])
			{
				f[l][r][0]=f[l+1][r][0]+cal(l,l+1);
				g[l][r][0]=l+1;
				h[l][r][0]=r;
				p[l][r][0]=0;
			}
			if(f[l+1][r][1]+cal(l,r)<f[l][r][0])
			{
				f[l][r][0]=f[l+1][r][1]+cal(l,r);
				g[l][r][0]=l+1;
				h[l][r][0]=r;
				p[l][r][0]=1;
			}
		}
	}
	// cout<<f[1][n][0]<<' '<<f[1][n][1]<<endl;
	if(f[1][n][0]<f[1][n][1]) out(1,n,0);
	else out(1,n,1);
    
    return 0;
}