小数据暴力+大数据贪心 = 95分

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1005;
int n, k;
struct Point
{
    double x, y;
} p[MAXN + 5];
double dis[MAXN + 5][MAXN + 5];
namespace case1
{
    // n<=9 枚举所有方案
    double ans;
    int id[10], path[10];
    void solve()
    {
        for (int i = 1; i <= n; i++)
            id[i] = i;
        ans = 1000 * 2e7;
        do
        {
            if (id[1] != k)
                continue;
            double now = 0;
            for (int i = 2; i <= n; i++)
                now += dis[id[i]][id[i - 1]];
            if (now < ans)
            {
                ans = now;
                for (int i = 1; i <= n; i++)
                    path[i] = id[i];
            }
        } while (next_permutation(id + 1, id + n + 1));
        for (int i = 1; i <= n; i++)
            cout << path[i] << " ";
        cout << "\n";
    }
}
namespace case2
{
    // n<=18 状压 dp
    double f[1 << 20][20]; // f[sta][last]: 走完了 sta 这些点，最后一次走的是 last 时的最短路径
    int path[1 << 20][20];
    vector<int> ans;
    void solve()
    {
        for (int sta = 0; sta <= (1 << n) - 1; sta++)
            for (int i = 1; i <= n; i++)
            {
                f[sta][i] = 1000 * 2e7;
                path[sta][i] = -1;
            }
        for (int sta = 0; sta <= (1 << n) - 1; sta++)
        {
            if ((sta & (1 << (k - 1))) == 0)
                continue; // 无效状态
            if (sta == (1 << (k - 1)))
            {
                f[sta][k] = 0;
                path[sta][k] = 0;
                continue;
            }
            for (int last = 1; last <= n; last++)
            {
                if ((sta & (1 << (last - 1))) == 0)
                    continue;
                int nxtSta = sta - (1 << (last - 1));
                for (int pre = 1; pre <= n; pre++)
                {
                    if (nxtSta & (1 << (pre - 1)) == 0)
                        continue;
                    if (f[nxtSta][pre] + dis[pre][last] < f[sta][last])
                    {
                        f[sta][last] = f[nxtSta][pre] + dis[pre][last];
                        path[sta][last] = pre;
                    }
                }
            }
        }
        int ansSta = (1 << n) - 1;
        int ansLast = 1;
        for (int i = 1; i <= n; i++)
            if (f[ansSta][i] < f[ansSta][ansLast])
                ansLast = i;
        ans.push_back(ansLast);
        while (path[ansSta][ansLast] != 0)
        {
            ans.push_back(path[ansSta][ansLast]);
            int temp = ansLast;
            ansLast = path[ansSta][ansLast];
            ansSta -= (1 << (temp - 1));
        }
        for (int i = ans.size() - 1; i >= 0; i--)
            cout << ans[i] << " ";
        cout << "\n";
    }
}
namespace case3
{
    // 贪心不停走最近的
    bool vis[MAXN + 5];
    vector<int> ans;
    void solve()
    {
        for (int i = 1; i <= n; i++)
            vis[i] = false;
        ans.push_back(k);
        vis[k] = true;
        int now = k;
        for (int i = 1; i <= n - 1; i++)
        {
            int nxt = -1;
            for (int j = 1; j <= n; j++)
            {
                if (vis[j])
                    continue;
                if (nxt == -1 || dis[now][j] < dis[now][nxt])
                    nxt = j;
            }
            ans.push_back(nxt);
            vis[nxt] = true;
        }
        for (int i = 0; i < ans.size(); i++)
            cout << ans[i] << " ";
        cout << "\n";
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    k = 0;
    for (int i = 1; i <= n; i++)
    {
        cin >> p[i].x >> p[i].y;
        if (k == 0 || p[i].y > p[k].y)
            k = i;
    }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            dis[i][j] = sqrt((p[i].x - p[j].x) * (p[i].x - p[j].x) +
                             (p[i].y - p[j].y) * (p[i].y - p[j].y));
    if (n <= 9)
        case1::solve();
    else if (n <= 18)
        case2::solve();
    else
        case3::solve();
    return 0;
}