#include using namespace std; using namespace chrono; #if __has_include() #include using namespace atcoder; #endif int main() { const auto start = steady_clock::now(); std::cin.tie(nullptr); std::ios_base::sync_with_stdio(false); int64_t n; cin >> n; vector as(n), bs(n); for (int64_t i = 0; i < n; i++) { cin >> as[i] >> bs[i]; } random_device rnd; mt19937 engine(rnd()); uniform_int_distribution<> randn(0, n - 1); int64_t c = 500000000000000000LL; auto calc_score = [&] { return int64_t(2000000 - 100000 * log10(max(abs(as[0] - c), abs(bs[0] - c)) + 1)); }; auto f = [&](int64_t a, int64_t b) { return max(abs(a - c), abs(b - c)); }; pair p = {2 * c - as[0], 2 * c - bs[0]}; auto g = [&](int64_t a, int64_t b) { return 2 * logl(abs(a - p.first) + abs(b - p.second)) / (logl(2 * abs(a - p.first)) + logl(abs(b - p.second))); }; using T = pair>, pair, vector>>; vector, greater<>>> pqs(50); for (int64_t i = 1; i < n; i++) { vector v; v.push_back(i); pqs[0].push({{g(as[i], bs[i]), v}, {as, bs}}); } long double s = (1LL << 60); vector xs; while (duration_cast(steady_clock::now() - start).count() < 900) { for (int64_t i = 0; i < 50; i++) { if (pqs[i].empty()) { continue; } auto [pp, qq] = pqs[i].top(); pqs[i].pop(); auto [d, v] = pp; auto [cs, ds] = qq; if (d < s) { s = d; xs = v; } if (i + 1 < 50) { for (int64_t k = 1; k < n; k++) { if (v.back() == k) { continue; } int64_t j = v.back(); v.push_back(k); int64_t w = cs[j], x = ds[j]; int64_t y = cs[k], z = ds[k]; cs[j] = cs[k] = (w + x) / 2; ds[j] = ds[k] = (y + z) / 2; pqs[i + 1].push({{g(cs[k], ds[k]), v}, {cs, ds}}); cs[j] = w; ds[j] = x; cs[k] = y; ds[k] = z; v.pop_back(); } } } } vector us, vs; for (int64_t i = 1; i < xs.size(); i++) { us.push_back(xs[i - 1] + 1); vs.push_back(xs[i] + 1); } us.push_back(1); vs.push_back([&] { int64_t ret = 1; for (int64_t i = 2; i < n; i++) { int64_t x = (as[0] + as[i]) / 2; int64_t y = (bs[0] + bs[i]) / 2; int64_t a = (as[0] + as[ret]) / 2; int64_t b = (bs[0] + bs[ret]) / 2; if (f(x, y) < f(a, b)) { ret = i; } } ret++; return ret; }()); cout << us.size() << '\n'; for (int64_t i = 0; i < us.size(); i++) { cout << us[i] << ' ' << vs[i] << '\n'; } cerr << calc_score() << endl; for (int64_t i = 0; i < n; i++) { cerr << as[i] << ' ' << bs[i] << endl; } return 0; }