写的区间DP，差不出错，状态转移方程如下：

$f(l,r,0)= \min \{ f(l+1,r,0)+dis(l+1,l),f(l+1,r,1)+dis(r,l) \}$

$f(l,r,1)= \min \{ f(l,r-1,0)+dis(l,r),f(l,r-1,1)+dis(r-1,r) \}$

代码如下：

#include <cmath>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const double inf=1e12;
struct Node{double x,y;};
int n,source;
double dis[1005][1005],f[1005][1005][2],pre[1005][1005][2];
Node pos[1005];
vector<int> ans;
inline double dist(const int A,const int B) {return sqrt((pos[A].x-pos[B].x)*(pos[A].x-pos[B].x)+(pos[A].y-pos[B].y)*(pos[A].y-pos[B].y));}
inline bool cmp(const Node A,const Node B) {return A.x<B.x;}
inline void print(const int l,const int r,const int Pos)
{
	int now=(Pos==0)?(l):(r);
	ans.push_back(now);
	if(now==source) return;
	if(f[l][r][0]<=f[l][r][1]) print(l+1,r,pre[l][r][0]);
	else print(l,r-1,pre[l][r][1]);
}
int main()
{
	scanf("%d",&n),pos[0].y=-inf;
	for(int i=1;i<=n;++i) scanf("%lf%lf",&pos[i].x,&pos[i].y);
	for(int i=n;i>=1;--i)
		if(pos[i].y>pos[source].y) source=i;
	for(int i=1;i<=n;++i)
		for(int j=i+1;j<=n;++j) dis[i][j]=dis[j][i]=dist(i,j);
	for(int i=0;i<=n+1;++i)
		for(int j=0;j<=n+1;++j) f[i][j][0]=f[i][j][1]=inf;
	f[source][source][0]=f[source][source][1]=0;
	for(int len=2;len<=n;++len)
		for(int l=1,r=l+len-1;r<=n;++l,++r)
		{
			if(f[l+1][r][0]+dis[l+1][l]<=f[l+1][r][1]+dis[r][l]) f[l][r][0]=f[l+1][r][0]+dis[l+1][l],pre[l][r][0]=0;
			else f[l][r][0]=f[l+1][r][1]+dis[r][l],pre[l][r][0]=1;
			if(f[l][r-1][0]+dis[l][r]<=f[l][r-1][1]+dis[r-1][r]) f[l][r][1]=f[l][r-1][0]+dis[l][r],pre[l][r][1]=0;
			else f[l][r][1]=f[l][r-1][1]+dis[r-1][r],pre[l][r][1]=1;
			f[l][r][0]=min(f[l][r][0],inf),f[l][r][1]=min(f[l][r][1],inf);
		}
	print(1,n,(f[1][n][0]<=f[1][n][1])?(0):(1));
	for(int i=(int)ans.size()-1;i>=0;--i) printf("%d ",ans[i]);
	return 0;
}

感觉没什么错，但只过了两个大样例。

而且一些样例看上去也不像凸包啊( ﾟ∀。)7