自己的逆天写法看不懂，但是AC

#include<bits/stdc++.h>
#define ll long long
#define ma 4145141
using namespace std;
const double inf = 1000000000000000000;
const ll mod = 19650827;

//---------------------------------------------
ll n;
struct nod {
	double x, y;
}a[ma];

//---------------------------------------------

double dis(ll i, ll j) {
	return sqrt((a[i].x - a[j].x) * (a[i].x - a[j].x) + (a[i].y - a[j].y) * (a[i].y - a[j].y));
}
bool cmp(nod a, nod b) {
	return a.x < b.x;
}
ll pos;
double f[2010][2010][2];
struct node {
	ll l, r, op;
}nxt[2010][2010][2];

//---------------------------------------------

int main() {
	std::ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin >> n;

	//----------------------------------init

	for (ll i = 1;i <= 2 * n;i++) {
		for (ll j = 1;j <= 2 * n;j++) {
			f[i][j][0] = f[i][j][1] = inf;
		}
	}

	for (ll i = 1;i <= n;i++) cin >> a[i].x >> a[i].y;
	for (ll i = 1;i <= n;i++) {
		if (a[pos].y < a[i].y) pos = i;
	}

	//-------------------------特判性质B，不知道为什么不判会错

	ll flag = 0;
	for (ll i = 1;i < n;i++) {
		if (a[i].x > a[i + 1].x || a[i].y < a[i + 1].y) flag = 1;
	}
	if (!flag) {
		for (ll i = 1;i <= n;i++) cout << i << " ";
		cout << endl;
		return 0;
	}

	//-------------------------DP

	for (ll i = 1;i <= n;i++) {
		a[i + n] = a[i];
		f[i][i][0] = f[i][i][1] = f[i + n][i + n][0] = f[i + n][i + n][1] = 0;
	}

	for (ll len = 2;len <= n;len++) {
		for (ll l = 1;l + len - 1 <= 2 * n;l++) {
			ll r = l + len - 1;

			//从 r 转移到 l

			if (f[l + 1][r][0] + dis(l, l + 1) > f[l + 1][r][1] + dis(l, r) && (r != pos || r != pos + n)) {
				if (f[l][r][0] > f[l + 1][r][1] + dis(l, r)) {
					f[l][r][0] = f[l + 1][r][1] + dis(l, r);
					nxt[l][r][0] = (node){ l + 1,r,1 };
				}
			}

			//从 l + 1 转移到 r

			else if (l + 1 != pos || l + 1 != pos + n) {
				if (f[l][r][0] > f[l + 1][r][0] + dis(l, l + 1)) {
					f[l][r][0] = f[l + 1][r][0] + dis(l, l + 1);
					nxt[l][r][0] = (node){ l + 1,r,0 };
				}
			}

			//从 l 转移到 r

			if (f[l][r - 1][1] + dis(r - 1, r) > f[l][r - 1][0] + dis(l, r) && (r - 1 != pos || r - 1 != pos + n)) {
				if (f[l][r][1] > f[l][r - 1][0] + dis(l, r)) {
					f[l][r][1] = f[l][r - 1][0] + dis(l, r);
					nxt[l][r][1] = (node){ l,r - 1,0 };
				}
			}

			//从 r - 1 转移到 l

			else if (l != pos || l != pos + n) {
				if (f[l][r][1] > f[l][r - 1][1] + dis(r - 1, r)) {
					f[l][r][1] = f[l][r - 1][1] + dis(r - 1, r);
					nxt[l][r][1] = (node){ l,r - 1,1 };
				}
			}
		}
	}

	//-------------------算答案

	double ans = inf;
	ans = min(ans, min(f[pos][pos + n - 1][0], f[pos + 1][pos + n][1]));

	//----------------------算路径

	vector<ll> rod;

	if (ans == f[pos][pos + n - 1][0]) {
		cout << pos << " ";
		ll l = nxt[pos][pos + n - 1][0].l, r = nxt[pos][pos + n - 1][0].r, op = nxt[pos][pos + n - 1][0].op;
		while (l) {
			if (op) rod.push_back(r);
			else rod.push_back(l);
			node res = nxt[l][r][op];
			l = res.l, r = res.r, op = res.op;
		}
		for (ll i = 0;i < (ll)rod.size();i++) cout << ((rod[i] % n) ? rod[i] % n : n) << " ";
		cout << endl;
		return 0;
	}

	cout << pos << " ";
	ll l = nxt[pos + 1][pos + n][1].l, r = nxt[pos + 1][pos + n][1].r, op = nxt[pos + 1][pos + n][1].op;
	while (l) {
		if (op) rod.push_back(r);
		else rod.push_back(l);
		node res = nxt[l][r][op];
		l = res.l, r = res.r, op = res.op;
	}
	for (ll i = 0;i < (ll)rod.size();i++) cout << ((rod[i] % n) ? rod[i] % n : n) << " ";
	cout << endl;
	return 0;
}