// #pragma GCC target("avx2") #pragma GCC optimize("O3") // #pragma GCC optimize("unroll-loops") #include // #include // #include using namespace std; // using mint = atcoder::modint998244353; const int M = 998244353; const long long LM = 1LL << 60; using P = pair; inline unsigned int get_rand() { static unsigned int y = 2463534242; return y ^= (y ^= (y ^= y << 13) >> 17) << 5; } long long calc(int i, int j, const vector& a, const vector& b) { const long long T = 500000000000000000LL; return max(abs(a[i] + a[j] - T * 2), abs(b[i] + b[j] - T * 2)); }; void op(int i, int j, vector& a, vector& b, vector

& ans) { if (i == j) return; if (ans.size() >= 50) return; ans.emplace_back(i, j); auto av = (a[i] + a[j]) / 2; auto bv = (b[i] + b[j]) / 2; a[i] = av; a[j] = av; b[i] = bv; b[j] = bv; } pair, long long> greedy(vector a, vector b, vector

ans, const vector

& init) { int n = a.size(); for (auto& i : init) { if (ans.size() < 50) { op(i.first, i.second, a, b, ans); } } while (ans.size() < 50) { int q = 0; for (int i = 1; i < n; ++i) { if (calc(0, q, a, b) > calc(0, i, a, b)) { q = i; } } if (q == 0) break; op(0, q, a, b, ans); } return { ans, calc(0, 0, a, b) }; } pair, long long> solve(vector a, vector b, int t) { int n = a.size(); vector

best_ans; long long best_score = LM; vector

ans; while ((int)ans.size() < 40) { int cp = -1, cq = -1; long long be = LM; for (int i = 0; i < n; ++i) { for (int j = i + 1; j < n; ++j) { long long cc = calc(i, j, a, b); if (cc < min(calc(i, i, a, b), calc(j, j, a, b))) { if (cp == -1 || cc < be) { cp = i; cq = j; be = cc; } } } } // vector

cand; // for (int i = 0; i < n; ++i) { // for (int j = i + 1; j < n; ++j) { // if (calc(i, j, a, b) < min(calc(i, i, a, b), calc(j, j, a, b))) { // cand.emplace_back(i, j); // } // } // } int p, q; if (cp != -1 && get_rand() % t) { // int i = get_rand() % cand.size(); // p = cand[i].first; // q = cand[i].second; p = cp; q = cq; } else { p = 1; q = get_rand() % n; while (p == q) { p = 1; q = get_rand() % n; } } op(p, q, a, b, ans); auto g = greedy(a, b, ans, {}); if (best_score > g.second) { best_ans = g.first; best_score = g.second; } for (int i = 1; i < n; ++i) { auto g = greedy(a, b, ans, {{0, i}}); if (best_score > g.second) { best_ans = g.first; best_score = g.second; } } } return { best_ans, best_score }; } int main() { cin.tie(0); ios::sync_with_stdio(0); int n; cin >> n; vector a(n), b(n); for (int i = 0; i < n; ++i) { cin >> a[i] >> b[i]; } vector

ans; long long score = LM; for (int _ = 0; _ < 200; ++_) { auto res = solve(a, b, _ % 2 ? 4 : 8); if (score > res.second) { ans = res.first; score = res.second; } } if (ans.size() > 50) { ans.resize(50); } cout << ans.size() << '\n'; for (auto& i : ans) { cout << i.first + 1 << ' ' << i.second + 1 << '\n'; } return 0; }