TIOJ 1928

/* TIOJ 1928 --- AC code by SorahISA */
/* https://tioj.ck.tp.edu.tw/problems/1928 */

#pragma GCC target("avx2")
#pragma GCC optimize("O3", "unroll-loops")

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

#define int long long
#define double long double

#define X first
#define Y second

#define fastIO() ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define RANDOM() random_device __rd; \
                 mt19937 __gen = mt19937(__rd()); \
                 uniform_int_distribution<int> __dis(0, MAXN); \
                 auto rnd = bind(__dis, __gen);

const int MAXN = 1E6;
const int maxn = 800 + 5;

pair<pair<int, int>, int> v[maxn];
double dp[maxn][maxn];
int fr[maxn][maxn];

double Dis(pair<int, int> a, pair<int, int> b) {
    return sqrt((a.X - b.X) * (a.X - b.X) + (a.Y - b.Y) * (a.Y - b.Y));
}

double Polar(pair<double, double> a, pair<int, int> b) {
    double tX = b.X, tY = b.Y;
    tX -= a.X, tY -= a.Y;
    // cerr << "Polar(" << b.X << ", " << b.Y << "): " << tY << "/" << tX << ": " << tY / tX << "\n";
    return tY / tX;
}

int Upper(pair<double, double> a, pair<int, int> b) {
    double tX = b.X, tY = b.Y;
    tX -= a.X, tY -= a.Y;
    return tY > 0;
}

void PrintAnswer(int L, int R) {
    if (L + 2 >= R) return;

    if (L + 1 < fr[L][R]) cout << v[L].Y << " " << v[fr[L][R]].Y << "\n";
    if (fr[L][R] + 1 < R) cout << v[fr[L][R]].Y << " " << v[R].Y << "\n";
    PrintAnswer(L, fr[L][R]);
    PrintAnswer(fr[L][R], R);
}

int32_t main() {
    fastIO();

    int n, tok = 0;
    double sX = 1e-6, sY = 1e-6;
    cin >> n;

    /// sort by Polar ///
    for (int i = 0; i < n; ++i) cin >> v[i].X.X >> v[i].X.Y, v[i].Y = tok++, sX += v[i].X.X, sY += v[i].X.Y;
    // cerr << "center(" << sX / n << ", " << sY / n << ")\n";
    sort(v, v + n, [&](auto a, auto b) {
        if (Upper({sX / n, sY / n}, a.X) != Upper({sX / n, sY / n}, b.X)) {
            return Upper({sX / n, sY / n}, a.X) == 1;
        }
        double scA = Polar({sX / n, sY / n}, a.X);
        double scB = Polar({sX / n, sY / n}, b.X);
        if ((scA > 0 and scB > 0) or (scA < 0 and scB < 0)) {
            return scA < scB;
        }
        return scA > scB;
    });

    /// dp and backtracking --- dp[i][j] = min(dp[i][k] + dp[k][j] + Dis(v[i], v[k])) ///
    for (int len = 4; len <= n; ++len) {
        for (int i = 0; i < n-len+1; ++i) {
            int j = i + len - 1;
            dp[i][j] = 1E12;
            fr[i][j] = j;

            /// connection from v[i] ///
            for (int k = i+2; k <= j; ++k) {
                if (dp[i][k] + dp[k][j] + Dis(v[i].X, v[k].X) + (k + 1 >= j ? 0 : Dis(v[k].X, v[j].X)) < dp[i][j]) {
                    dp[i][j] = dp[i][k] + dp[k][j] + Dis(v[i].X, v[k].X) + (k + 1 == j ? 0 : Dis(v[k].X, v[j].X));
                    fr[i][j] = k;
                }
            }

            /// connection from v[j] ///
            if (dp[i + 1][j] + Dis(v[i + 1].X, v[j].X) < dp[i][j]) {
                dp[i][j] = dp[i + 1][j] + Dis(v[i + 1].X, v[j].X);
                fr[i][j] = i + 1;
            }

            /// Doing dp from both side cause TLE ///
            /*
            for (int k = j-2; k >= i; --k) {
                if (dp[i][k] + dp[k][j] + Dis(v[k].X, v[j].X) + (k - 1 <= i ? 0 : Dis(v[i].X, v[k].X)) < dp[i][j]) {
                    dp[i][j] = dp[i][k] + dp[k][j] + Dis(v[k].X, v[j].X) + (k - 1 <= i ? 0 : Dis(v[i].X, v[k].X));
                    fr[i][j] = k;
                }
            }
            */
        }
    }

    /*
    cout << fixed << setprecision(10);

    for (int i = 0; i < n; ++i) cerr << v[i].X.X << " " << v[i].X.Y << ": " << v[i].Y << "\n";

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cerr << dp[i][j] << "\t\n"[j == n-1];
        }
    }
    */

    /// Recurse to print answer ///
    PrintAnswer(0, n - 1);

    return 0;
}