// #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 long long get_usec() { timeval tv; gettimeofday(&tv, NULL); return (long long)tv.tv_sec * 1000000 + tv.tv_usec; } 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]) / 2 - T), abs((b[i] + b[j]) / 2 - T)); }; 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; vector> table(n, vector(n)); for (int i = 0; i < n; ++i) { for (int j = i; j < n; ++j) { table[i][j] = calc(i, j, a, b); } } priority_queue, vector>, greater>> cand; // set> cand; for (int i = 0; i < n; ++i) { for (int j = i + 1; j < n; ++j) { if (table[i][j] < table[i][i] && table[i][j] < table[j][j]) { cand.emplace(table[i][j], P(i, j)); } } } while ((int)ans.size() < 45) { // 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; // } // } // } // } int p = -1; int q = -1; while (!cand.empty()) { auto& top = cand.top(); int i = top.second.first; int j = top.second.second; if (top.first != table[i][j] || table[i][j] >= table[i][i] || table[i][j] >= table[i][i]) { cand.pop(); } else { break; } } if (!cand.empty() && get_rand() % max(1, t - (int)ans.size())) { p = cand.top().second.first; q = cand.top().second.second; cand.pop(); // if (cp != -1 && get_rand() % t) { // p = cp; // q = cq; } else { p = 0; // p = get_rand() % n; q = get_rand() % n; while (p == q) { p = 0; // p = get_rand() % n; q = get_rand() % n; } } op(p, q, a, b, ans); if (t - (int)ans.size() > 1) { for (int i = 0; i < p; ++i) { table[i][p] = calc(i, p, a, b); } for (int j = p; j < n; ++j) { table[p][j] = calc(p, j, a, b); } for (int i = 0; i < q; ++i) { table[i][q] = calc(i, q, a, b); } for (int j = q; j < n; ++j) { table[q][j] = calc(q, j, a, b); } for (int i = 0, j = p; i < p; ++i) { if (table[i][j] < table[i][i] && table[i][j] < table[j][j]) { cand.emplace(table[i][j], P(i, j)); } } for (int j = p + 1, i = p; j < n; ++j) { if (table[i][j] < table[i][i] && table[i][j] < table[j][j]) { cand.emplace(table[i][j], P(i, j)); } } for (int i = 0, j = q; i < q; ++i) { if (table[i][j] < table[i][i] && table[i][j] < table[j][j]) { cand.emplace(table[i][j], P(i, j)); } } for (int j = q + 1, i = q; j < n; ++j) { if (table[i][j] < table[i][i] && table[i][j] < table[j][j]) { cand.emplace(table[i][j], P(i, j)); } } } else { cand = {}; } 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; // vector t = { 4, 8 }; auto start = get_usec(); for (int _ = 0; get_usec() - start < 900000; ++_) { auto res = solve(a, b, _ % 45 + 1); 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; }