#include <bits/stdc++.h>
using namespace std;

const int maxn = 3e3 + 5;
const long long inf = 1e10 + 7;
int n, k, st, p, q;
double x[maxn], y[maxn], f[maxn][maxn][2];
vector<int> seq;

double dis(int a, int b)
{
    return sqrt((x[a] - x[b]) * (x[a] - x[b]) +
                (y[a] - y[b]) * (y[a] - y[b]));
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> x[i] >> y[i];
        x[i + n] = x[i], y[i + n] = y[i];
        if (y[i] > y[k])
            k = i;
    }
    for (int i = 0; i <= 2 * n; i++)
        for (int j = i; j <= 2 * n; j++)
            f[i][j][0] = f[i][j][1] = inf;
    f[k][k][0] = f[k][k][1] = 0;
    f[k + n][k + n][0] = f[k + n][k + n][1] = 0;
    for (int len = 1; len <= n; len++)
        for (int i = 0; i + len < n * 2; i++)
        {
            int j = i + len;
            f[i][j][0] = min(f[i][j][0], f[i + 1][j][1] + dis(i, j));
            f[i][j][0] = min(f[i][j][0], f[i + 1][j][0] + dis(i, i + 1));
            f[i][j][1] = min(f[i][j][1], f[i][j - 1][0] + dis(i, j));
            f[i][j][1] = min(f[i][j][1], f[i][j - 1][1] + dis(j - 1, j));
        }
    for (int i = 0; i < n; i++)
        for (int j = 0; j < 2; j++)
            if (f[i][i + n - 1][j] < f[p][p + n - 1][st])
                p = i, st = j;
    q = p + n - 1;
    for (int r = 0; r < n; r++)
    {
        if (st == 0)
        {
            st = (f[p + 1][q][0] + dis(p, p + 1) >
                  f[p + 1][q][1] + dis(q, p));
            seq.push_back(p % n + 1), p++;
        }
        else
        {
            st = (f[p][q - 1][0] + dis(p, q) >
                  f[p][q - 1][1] + dis(q - 1, p));
            seq.push_back(q % n + 1), q--;
        }
    }
    for (int i = seq.size() - 1; i >= 0; i--)
        cout << seq[i] << ' ';
    return 0;
}

WA on #5、#8、#9、#17~#20。

应该是小问题。