#pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #include #include using namespace std; // #include // using namespace atcoder; #define rep(i, n) for (int i = 0; i < (n); ++i) #define ll long long static constexpr ll INF = 1e18; static constexpr int inf = 1e9; const double TIME_LIMIT = 990; const long long VAL = 5e17; const int OP_SIZE = 50; const long long N = 45; long long A[N]; long long B[N]; // Random namespace titan23 { struct Random { unsigned int _x, _y, _z, _w; Random() { _x = 123456789; _y = 362436069; _z = 521288629; _w = 88675123; } unsigned int _xor128() { unsigned int t = _x ^ (_x << 11); _x = _y; _y = _z; _z = _w; _w = (_w ^ (_w >> 19)) ^ (t ^ (t >> 8)); return _w; } double random() { return (double)(_xor128()) / 0xFFFFFFFF; } int randint(int begin, int end) { assert(begin <= end); return begin + _xor128() % (end - begin + 1); } double randdouble(double begin, double end) { assert(begin < end); return begin + random() * (end-begin); } int randrange(int begin, int end) { assert(begin < end); return begin + _xor128() % (end - begin); } template void shuffle(vector &a) { int n = (int)a.size(); for (int i = 0; i < n-1; ++i) { int j = randrange(i, n); swap(a[i], a[j]); } } template T choice(const vector &a) { int i = randrange(0, a.size()); return a[i]; } template T choice(const vector &a, const vector &w, bool normal) { assert(normal == false); assert(a.size() == w.size()); double sum = 0.0; for (const int &x: w) sum += x; assert(sum > 0); vector x(w.size()); for (int i = 0; i < x.size(); ++i) { x[i] = (double)w[i] / sum; if (i-1 >= 0) x[i] += x[i-1]; } return choice(a, x); } template T choice(const vector &a, const vector &w) { double i = random(); int l = -1, r = a.size()-1; while (r - l > 1) { int mid = (l + r) / 2; if (w[mid] <= i) l = mid; else r = mid; } return a[r]; } }; } // namespace titan23 titan23::Random myrandom; // Timer namespace titan23 { class Timer { public: Timer() : start_timepoint(std::chrono::high_resolution_clock::now()) {} void reset() { start_timepoint = std::chrono::high_resolution_clock::now(); } double elapsed() { auto end_timepoint = std::chrono::high_resolution_clock::now(); auto start = std::chrono::time_point_cast(start_timepoint).time_since_epoch().count(); auto end = std::chrono::time_point_cast(end_timepoint).time_since_epoch().count(); return (end - start) * 0.001; // ミリ秒単位で経過時間を返す } private: std::chrono::time_point start_timepoint; }; } // SA 最小化 namespace titan23 { namespace sa { titan23::Random sa_random; using Changed = vector>; struct State { double score; vector> op; State() : score(0.0) {} double get_score() const { ll a[N], b[N]; rep(i, N) { a[i] = A[i]; b[i] = B[i]; } for (auto &[u, v]: op) { ll x = (a[u]+a[v])/2; a[u] = x; a[v] = x; ll y = (b[u]+b[v])/2; b[u] = y; b[v] = y; } return max(abs(VAL-a[0]), abs(VAL-b[0])) / 1e4; } Changed modify() { vector> pre_op = op; double prob = myrandom.random(); if (op.empty() || (prob < 0.1 && op.size()+1 <= OP_SIZE)) { int indx = myrandom.randint(0, op.size()); int u = myrandom.randrange(0, N); int v = myrandom.randrange(0, N); while (u == v) { v = myrandom.randrange(0, N); } pair uv = {u, v}; op.insert(op.begin()+indx, uv); } else { assert(!op.empty()); int indx = myrandom.randrange(0, op.size()); op.erase(op.begin() + indx); } return pre_op; } void rollback(Changed &changed) { op = changed; } }; // TIME_LIMIT: ms State run(const double TIME_LIMIT) { titan23::Timer sa_timer; double START_TEMP = 100.0; double END_TEMP = 1.0; double TEMP_VAL = (START_TEMP - END_TEMP) / TIME_LIMIT; auto make_ans_init = [&] () -> State { State state; return state; }; State ans = make_ans_init(); State best_ans = ans; double score = ans.get_score(); double best_score = score; int cnt = 0; while (true) { double now_time = sa_timer.elapsed(); if (now_time > TIME_LIMIT) break; ++cnt; Changed changed = ans.modify(); double new_score = ans.get_score(); double arg = score - new_score; if (arg >= 0 || exp(arg/(START_TEMP-TEMP_VAL*now_time)) > sa_random.random()) { score = new_score; if (score < best_score) { best_score = score; best_ans = ans; } } else { ans.rollback(changed); } } cerr << "cnt=" << cnt << endl; cerr << "score=" << best_score << endl; return best_ans; } } } // namespace titan23 using namespace titan23; void solve() { int n_; cin >> n_; rep(i, N) cin >> A[i] >> B[i]; sa::State ans = sa::run(TIME_LIMIT); cout << ans.op.size() << endl; for (auto &[u, v]: ans.op) { cout << u+1 << ' ' << v+1 << endl; } } int main() { ios::sync_with_stdio(false); cin.tie(0); solve(); return 0; }