6

开始部分分A(#13 #14)没打对交上去拿了95pts、WA了#14，直接整乐了。

合着无特殊性质的数据比有特殊性质的数据还要水？

改好部分分之后就A了。

#include <bits/stdc++.h>
#define rep(i, l, r) for(int i = l; i < r; i++)
#define hrp(i, l, r) for(int i = l; i <= r; i++)
#define rev(i, r, l) for(int i = r; i >= l; i--)
#define ms(n, t) memset(n, t, sizeof(n))
#define pb push_back
using namespace std;
const int U = 1e4;
double x[U], y[U];
bool vis[U];
double dp[(1<<18)+500][18];
int lst[(1<<18)+500][18];
double dis(int a, int b)
{
	return sqrt((x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b]));
}
signed main(void)
{
	int n;
	cin>>n;
	rep(i, 0, n) cin>>x[i]>>y[i];

	bool B = 1;
	rep(i, 1, n)
	{
		if (x[i] <= x[i-1]) B = 0;
		if (y[i] >= y[i-1]) B = 0;
	}

	int k;
	double maxy = -1e100;
	rep(i, 0, n) if (y[i] > maxy) maxy = y[i], k = i;

	double ans = 0;
	if (B) rep(i, 0, n) cout<<i+1<<' ';
	else if (n <= 20)
	{
		rep(i, 0, 1<<n) rep(j, 0, 18) dp[i][j] = 1e100;
		dp[1<<k][k] = 0;

		rep(msk, 0, 1<<n)
		{
			rep(to, 0, n)
			{
				if ((msk>>to)&1) continue;
				rep(from, 0, n)
				{
					if (!((msk>>from)&1)) continue;
					if (dp[(1<<to)|msk][to] > dp[msk][from]+dis(from, to))
					{
						dp[(1<<to)|msk][to] = dp[msk][from]+dis(from, to);
						lst[(1<<to)|msk][to] = from;
					}
				}
			}
		}

		double minn = (double)1e100;
		int last;
		rep(i, 0, 18) if (minn > dp[(1<<n)-1][i]) minn = dp[(1<<n)-1][i], last = i;

		vector<int> v;
		v.pb(last);
		int msk = (1<<n)-1;
		rep(i, 0, n-2)
		{
			int l = lst[msk][last];
			v.pb(l);
			msk ^= 1<<last;
			last = l;
		}
		v.pb(k);
		reverse(v.begin(), v.end());

		rep(i, 0, n) cout<<v[i]+1<<' ';
	}
	else
	{
		vector<int> v1{k}, v2{k};
		vis[k] = 1;
		while(v1.size() < n)
		{
			double mindis = 1e100;
			int lst = v1.back(), t;
			rev(i, n-1, 0) if (!vis[i] && mindis-dis(lst, i) > 1e-7) mindis = dis(lst, i), t = i;
			v1.pb(t);
			vis[t] = 1;
		}

		ms(vis, 0);
		vis[k] = 1;
		while(v2.size() < n)
		{
			double mindis = 1e100;
			int lst = v2.back(), t;
			rep(i, 0, n) if (!vis[i] && mindis-dis(lst, i) > 1e-7) mindis = dis(lst, i), t = i;
			v2.pb(t);
			vis[t] = 1;
		}

		double ans1 = 0, ans2 = 0;
		rep(i, 1, n)
		{
			ans1 += dis(v1[i], v1[i-1]);
			ans2 += dis(v2[i], v2[i-1]);
		}

		if (ans1 > ans2) rep(i, 0, n) cout<<v2[i]+1<<' ';
		else rep(i, 0, n) cout<<v1[i]+1<<' ';
	}

	return 0;
}