rt,从k号点开始，每次选择连到左边的点还是右边的点，用dp解决，以这张图为例 从5开始走，会走出5->4->3->6->...或5->6->4->3->2->...之类的路径，但不会出现5->2->6->...这样跨点走的路径

代码如下

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e3 + 5;

int s[MAXN];
int cnt = 0;

double dp[MAXN][MAXN][2];

struct Node {
  double x, y;
  Node operator-(const Node& xx) const { return {x - xx.x, y - xx.y}; }
} a[MAXN];

double x(Node a, Node b) {
  return a.x * b.y - a.y * b.x;
}

double l(Node &a, Node &b) {
  return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}

double dis(Node &a, Node &b) {
  return sqrt(l(a, b));
}

bool cmp(Node a1, Node a2) {
  if (x(a1 - a[0], a2 - a[0]) != 0) {
    return x(a1 - a[0], a2 - a[0]) > 0;
  }
  return l(a1, a[0]) < l(a2, a[0]);
}

int anss[MAXN];

int main() {
  cin.tie(0), cout.tie(0);
  ios_base::sync_with_stdio(0);
  int n, k = 0;
  double ans = 1e12;
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> a[i].x >> a[i].y;
  }
  double minx = 1145141919, miny = 1145141919, maxy;
  int mini;
  // for (int i = 0; i < n; i++) { //(这个傻逼没看清题目以为点是不按照凸边形顺序给的然后脑残写了个凸包)
  //   if (a[i].x < minx || (a[i].x == minx && a[i].y < miny)) {
  //     minx = a[i].x, miny = a[i].y, mini = i;
  //   }
  // }
  // swap(a[0], a[mini]);
  // sort(a + 1, a + n, cmp);
  // s[cnt++] = 0;
  // for (int i = 1; i <= n; i++) {
  //   while (x(a[s[cnt - 1]] - a[s[cnt - 2]], a[i % n] - a[s[cnt - 1]]) < 0) {
  //     cnt--;
  //   }
  //   s[cnt++] = i % n;
  // }
  for (int i = 0; i <= n; i++) {
    s[i] = i;
  }
  maxy = a[s[0]].y;
  for (int i = 1; i < n; ++i) {
    if (maxy < a[s[i]].y) {
      maxy = a[s[i]].y;
      k = i;
    }
  }

  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      dp[i][j][0] = dp[i][j][1] = 1e12;
    }
  }
  dp[0][0][0] = dp[0][0][1] = 0;
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j + i + 1 < n; ++j) {
      int uu0 = s[(n * 2 + k - i) % n], uu1 = s[(k + j) % n], vv0 = s[(2 * n + k - i - 1) % n], vv1 = s[(k + j + 1) % n];
      dp[i + 1][j][0] = min(dp[i][j][0] + dis(a[uu0], a[vv0]), dp[i][j][1] + dis(a[uu1], a[vv0]));
      dp[i][j + 1][1] = min(dp[i][j][0] + dis(a[uu0], a[vv1]), dp[i][j][1] + dis(a[uu1], a[vv1]));
    }
  }
  int ii, jj, ff;
  for (int i = 0, j; i < n; ++i) {
    j = n - i - 1;
    if (ans > dp[i][j][0]) {
      ii = i, jj = j, ff = 0;
      ans = dp[i][j][0];
    }
    if (ans > dp[i][j][1]) {
      ii = i, jj = j, ff = 1;
      ans = dp[i][j][1];
    }
  }
  int cntt = 0;
  anss[cntt++] = (k + jj) % n;
  while (ii || jj) {
    if (!ff) {
      int i = ii - 1, j = jj;
      int uu0 = s[(n * 2 + k - i) % n], uu1 = s[(k + j) % n], vv0 = s[(2 * n + k - i - 1) % n], vv1 = s[(k + j + 1) % n];
      if (dp[i + 1][j][0] == dp[i][j][0] + dis(a[uu0], a[vv0])) {
        ii = i, jj = j, ff = 0;
        anss[cntt++] = (2 * n + k - ii) % n;
      } else if (dp[i + 1][j][0] == dp[i][j][1] + dis(a[uu1], a[vv0])) {
        ii = i, jj = j, ff = 1;
        anss[cntt++] = (k + jj) % n;
      }
    } else {
      int i = ii, j = jj - 1;
      int uu0 = s[(n * 2 + k - i) % n], uu1 = s[(k + j) % n], vv0 = s[(2 * n + k - i - 1) % n], vv1 = s[(k + j + 1) % n];
      if (dp[i][j + 1][1] == dp[i][j][0] + dis(a[uu0], a[vv1])) {
        ii = i, jj = j, ff = 0;
        anss[cntt++] = (2 * n + k - ii) % n;
      } else {
        ii = i, jj = j, ff = 1;
        anss[cntt++] = (k + jj) % n;
      }
    }
  }
  // printf("%.4lf", ans);
  for (int i = cntt - 1; i > -1; --i) {
    cout << anss[i] + 1 << ' ';
  }
  return 0;
}