思路：队列优化的区间DP

#include<bits/stdc++.h>
#define re register
using namespace std;
long double dp[2005][2005][1];
bool used[2005][2005][1];
struct Q1{
	long double x;
	long double y;
}C1[1005],C2[2005];
struct Q2{
	int left;
	int right;
	int dir;
	queue<int> num; 
}; 
int n;
Q2 ans;
long double ton=1000000000;
stack<int> line;
queue<Q2> seq;
vector<int> output;
template<typename T>inline void qread(T &x)
{
x=0;int f=0;char ch=getchar();
while(ch<'0'||ch>'9') {f|=(ch=='-');ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
x=f?-x:x;
return;
}
inline long double cal(long double x1,long double y1,long double x2,long double y2){
	return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
inline int query(int x){
	return x%n==0?n:x%n;
}
inline void segment(const Q2 &s){
	int x,y,z;
	x=s.left;y=s.right;z=s.dir;
	if(z==0){
		if(y-x<n-1){
			dp[x-1][y][0]=min(dp[x-1][y][0],dp[x][y][0]+cal(C2[x].x,C2[x].y,C2[x-1].x,C2[x-1].y));
			if(used[x-1][y][0]==0){
				used[x-1][y][0]=1;
				Q2 q;
				q.left=x-1;q.right=y;q.dir=0;
				q.num=s.num;
				q.num.push(0);
				seq.push(q);
			}
			dp[x][y+1][1]=min(dp[x][y+1][1],dp[x][y][0]+cal(C2[x].x,C2[x].y,C2[y+1].x,C2[y+1].y));
			if(used[x][y+1][1]==0){
				used[x][y+1][1]=1;
				Q2 q;
				q.left=x;q.right=y+1;q.dir=1;
				q.num=s.num;
				q.num.push(1);
				seq.push(q);
			}
		}
		if(y-x==n-1){
			if(dp[x][y][0]<ton){
				ton=dp[x][y][0];
				ans.num=s.num;
			}
		}
	}
	if(z==1){
		if(y-x<n-1){
			dp[x-1][y][0]=min(dp[x-1][y][0],dp[x][y][1]+cal(C2[y].x,C2[y].y,C2[x-1].x,C2[x-1].y));
			if(used[x-1][y][0]==0){
				used[x-1][y][0]=1;
				Q2 q;
				q.left=x-1;q.right=y;q.dir=0;
				q.num=s.num;
				q.num.push(0);
				seq.push(q);
			}
			dp[x][y+1][1]=min(dp[x][y+1][1],dp[x][y][1]+cal(C2[y].x,C2[y].y,C2[y+1].x,C2[y+1].y));
			if(used[x][y+1][1]==0){
				used[x][y+1][1]=1;
				Q2 q;
				q.left=x;q.right=y+1;q.dir=1;
				q.num=s.num;
				q.num.push(1);
				seq.push(q);
			}
		}
		if(y-x==n-1){
			if(dp[x][y][1]<ton){
				ton=dp[x][y][1];
				ans.num=s.num;
			}
		}
	}
}
int main(){
	int p=-1e9,t=0;
	qread(n);
	for(re int i=1;i<=n;i++){
		cin>>C1[i].x>>C1[i].y;
		if(C1[i].y>p){
			p=C1[i].y;
			t=i;
		}
	}
	for(re int i=1;i<=n<<1;i++){
		for(re int j=1;j<=n<<1;j++){
			dp[i][j][0]=10e9;
			dp[i][j][1]=10e9;
		}
	}
	for(re int i=1;i<=n<<1;i++){
		C2[i].x=C1[query(t+i)].x;
		C2[i].y=C1[query(t+i)].y;
	}//破环为链 
	dp[n][n][0]=0;
	dp[n][n][1]=0;
	Q2 q;
	q.left=n;q.right=n;q.dir=0;
	seq.push(q);
	while(!seq.empty()){
		segment(seq.front());
		seq.pop();
	}
	int head=n+t,tail=n+t;
	output.push_back(n+t);
	while(!ans.num.empty()){
		int l=ans.num.front();
		ans.num.pop();
		if(l==0){
			head--;
			output.push_back(head);
		}
		if(l==1){
			tail++;
			output.push_back(tail);
		}
	}
	for(re int i=0;i<output.size();i++){
		cout<<query(output[i])<<" ";
	}
	return 0;
}