救救孩子吧

#include<iostream>
#include<cmath>
using namespace std;
int n,k=1;
struct point{
    long double x,y;
}ps[2048];
long double f[2048][2048][2];
long double dis[2048][2048];
int pre[2048][2048][2][3];
inline long double getdis(const point& a,const point& b)
{
    return sqrtl(static_cast<long double>(a.x-b.x)*(a.x-b.x)+static_cast<long double>(a.y-b.y)*(a.y-b.y));
}
void print(int i,int j,int mod)
{
    if(i==j)
    {
        printf("%d",i>n?i-n:i);
        return;
    }
    print(pre[i][j][mod][0],pre[i][j][mod][1],pre[i][j][mod][2]);
    if(mod)
        printf(" %d",j>n?j-n:j);
    else printf(" %d",i>n?i-n:i);
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>ps[i].x>>ps[i].y;
        if(ps[i].y>ps[k].y)
            k=i;
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            dis[i][j]=dis[i+n][j]=dis[i][j+n]=dis[i+n][j+n]=getdis(ps[i],ps[j]);
    for(int i=0;i<=n*2;i++)
        for(int j=0;j<=n*2;j++)
            f[i][j][0]=f[i][j][1]=1e32;
    f[k][k][0]=f[k][k][1]=f[k+n][k+n][0]=f[k+n][k+n][1]=0;
    for(int len=2;len<=n;len++)
        for(int i=1;i+len-1<=n*2;i++)
        {
            int j=i+len-1;
            if(f[i+1][i][0]+dis[i][i+1]>f[i+1][j][1]+dis[i][j])
            {
                f[i][j][0]=f[i+1][j][1]+dis[i][j];
                pre[i][j][0][0]=i+1;
                pre[i][j][0][1]=j;
                pre[i][j][0][2]=1;
            }
            else
            {
                f[i][j][0]=f[i+1][j][0]+dis[i][i+1];
                pre[i][j][0][0]=i+1;
                pre[i][j][0][1]=j;
                pre[i][j][0][2]=0;
            }
            if(f[i][j-1][0]+dis[i][j]>f[i][j-1][1]+dis[j-1][j])
            {
                f[i][j][1]=f[i][j-1][1]+dis[j-1][j];
                pre[i][j][1][0]=i;
                pre[i][j][1][1]=j-1;
                pre[i][j][1][2]=1;
            }
            else
            {
                f[i][j][1]=f[i][j-1][0]+dis[i][j];
                pre[i][j][1][0]=i;
                pre[i][j][1][1]=j-1;
                pre[i][j][1][2]=0;
            }
        }
    int resi=0,resj=0,resmod=0;
    for(int i=1;i<=n;i++)
    {
        if(f[resi][resj][resmod]>f[i][i+n-1][0])
        {
            resi=i;
            resj=i+n-1;
            resmod=0;
        }
        if(f[resi][resj][resmod]>f[i][i+n-1][1])
        {
            resi=i;
            resj=i+n-1;
            resmod=1;
        }
    }
    print(resi,resj,resmod);
    return 0;
}