#include #include using ll = long long; using ull = unsigned long long; #define rep(i, n) for(int i = 0; i < (int)(n); i++) #define REP(i, m, n) for(int i = (int)(m); i < (int)(n); i++) using namespace std; using namespace atcoder; using mint = modint998244353; const int inf = 1000000007; const ll longinf = 1ll << 60; struct Timer { chrono::system_clock::time_point start, last_updated; Timer() { start = chrono::system_clock::now(); last_updated = chrono::system_clock::now(); } void reset() { start = chrono::system_clock::now(); } void update() { last_updated = chrono::system_clock::now(); } double getTime() { auto now = chrono::system_clock::now(); return chrono::duration(now - start).count(); } double should_finish_search1() { return getTime() > 5.8; } bool should_reset() { auto now = chrono::system_clock::now(); return chrono::duration(now - last_updated).count() > 1.0 || chrono::duration(now - start).count() > 5.8; } }; Timer timer; struct Xor128 { unsigned x, y, z, w; Xor128() : x(123456789), y(362436069), z(521288629), w(88675123){}; inline unsigned xor128() { unsigned t; t = x ^ (x << 11); x = y; y = z; z = w; return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)); } int nextInt(int x, int y) { return xor128() % (y - x) + x; } double nextDouble(double a, double b) { return (double)(xor128() & 0xffff) / 0xffff * (b - a) + a; } }; auto rnd = Xor128(); double calculate_score(ll x) { return 2000000 - 100000 * log10(abs(x) + 1); } double calculate_current_score(vector &a, vector &b, double t) { double ret = 0; double bumbo = 0; rep(i, a.size()) { double res = min(calculate_score(a[i]), calculate_score(b[i])); double b = 1; // if(i > 0) { // double c = (1 - t); // res *= c; // b = c; // } if(i == 0) { ret += res; bumbo += b; } } return ret / bumbo; } void output(vector> &query) { cout << query.size() << endl; for(auto [l, r] : query) { cout << l + 1 << " " << r + 1 << endl; } } void do_query(vector &a, vector &b, int i, int j) { ll x = (a[i] + a[j]) / 2; ll y = (b[i] + b[j]) / 2; a[i] = a[j] = x; b[i] = b[j] = y; } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n; cin >> n; vector a(n), b(n); rep(i, n) { cin >> a[i] >> b[i]; a[i] -= 5e17; b[i] -= 5e17; } vector> query; vector a_state = a, b_state = b; rep(_, 50) { int x = rnd.nextInt(0, n); int y = rnd.nextInt(0, n - 1); if(y >= x) ++y; query.emplace_back(x, y); do_query(a_state, b_state, x, y); } double t0 = 1e5; double t1 = 100; double tl = 0.95; double t = 0; int itr = 0; double time = 0; double best_score = 0; vector> best_query; while(1) { if(!(itr & 31)) { time = timer.getTime() / tl; if(time > 1.0) break; t = pow(t0, 1 - time) * pow(t1, time); } double cur = calculate_current_score(a_state, b_state, time); vector na = a, nb = b; int idx = rnd.nextInt(0, 50); int x, y; int type = rnd.nextInt(0, 6); if(type == 0) { x = rnd.nextInt(0, n), y = rnd.nextInt(0, n - 1); if(y >= x) ++y; } else if(type == 1) { x = query[idx].first, y = rnd.nextInt(0, n - 1); if(y >= x) ++y; } else if(type == 2) { y = query[idx].second, x = rnd.nextInt(0, n - 1); if(x >= y) ++x; } else { x = 0, y = rnd.nextInt(1, n); } rep(j, 50) { if(j == idx) { do_query(na, nb, x, y); } else { do_query(na, nb, query[j].first, query[j].second); } } double nxt = calculate_current_score(na, nb, time); double prob = exp((nxt - cur) / t); if(rnd.nextDouble(0, 1) < prob) { query[idx] = {x, y}; a_state = na; b_state = nb; double score = min(calculate_score(na[0]), calculate_score(nb[0])); if(score > best_score) { best_query = query; best_score = score; } } } output(best_query); for(auto [l, r] : best_query) { do_query(a, b, l, r); } rep(i, n) { cerr << a[i] << " " << b[i] << endl; } cerr << 50 * min(calculate_score(a[0]), calculate_score(b[0])) << endl; return 0; }