#pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #include #include using namespace std; #define rep(i, n) for (int i = 0; i < (n); ++i) #define ll long long #define double float static constexpr ll INF = 2e18; static constexpr const double TIME_LIMIT = 993; static constexpr const long long VAL = 5e17; static constexpr const int OP_SIZE = 50; static constexpr const long long N = 45; long long A[N]; long long B[N]; template T abs(const T &a, const T &b) { return a T max(const T &a, const S &b) { return a T min(const T &a, const S &b) { return a> 19)) ^ (t ^ (t >> 8)); return _w; } double random() { return (double)(_xor128()) / 0xFFFFFFFF; } int randint(const int begin, const int end) { return begin + _xor128() % (end - begin + 1); } int randrange(const int begin, const int end) { return begin + _xor128() % (end - begin); } }; } // 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; struct Changed { double pre_score; int type; int indx; pair uv; int indx1, indx2; Changed() {} Changed(double score) : pre_score(score) {} }; struct State { double score; vector> op; State() : score(0.0) {} void calc_score() { ll a[N], b[N]; memcpy(a, A, N * sizeof(ll)); memcpy(b, B, N * sizeof(ll)); for (const auto &[u, v]: op) { a[u] = a[v] = (a[u]+a[v])/2; b[u] = b[v] = (b[u]+b[v])/2; } score = log(max(abs(VAL-a[0]), abs(VAL-b[0]))); } double get_score() { return score; } Changed modify() { Changed changed(score); double prob = myrandom.random(); if (op.empty() || (prob < 0.1 && op.size()+1 <= OP_SIZE)) { changed.type = 0; 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); changed.indx = indx; } else if (prob < 0.12) { changed.type = 1; int indx = myrandom.randrange(0, op.size()); changed.indx = indx; changed.uv = op[indx]; op.erase(op.begin() + indx); } else if (prob < 0.81) { changed.type = 10; { int indx = myrandom.randrange(0, op.size()); changed.indx1 = indx; changed.uv = op[indx]; op.erase(op.begin() + indx); } { 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}; changed.indx2 = indx; op.insert(op.begin()+indx, uv); } } else if (prob < 0.96) { changed.type = 2; int indx = myrandom.randrange(0, op.size()); int u = myrandom.randrange(0, N); int v = myrandom.randrange(0, N); while (u == v) { v = myrandom.randrange(0, N); } changed.indx = indx; changed.uv = op[indx]; pair uv = {u, v}; op[indx] = uv; } else { changed.type = 3; int indx = myrandom.randrange(0, op.size()); auto [pre_u, pre_v] = op[indx]; int u = pre_u, v = pre_v; if (myrandom.random() < 0.4) { u = myrandom.randrange(0, N); while (u == pre_u || u == pre_v) { u = myrandom.randrange(0, N); } } else { v = myrandom.randrange(0, N); while (v == pre_v || v == pre_u) { v = myrandom.randrange(0, N); } } changed.indx = indx; changed.uv = op[indx]; pair uv = {u, v}; op[indx] = uv; } calc_score(); return changed; } void rollback(Changed &changed) { if (changed.type == 0) { op.erase(op.begin() + changed.indx); } else if (changed.type == 1) { op.insert(op.begin() + changed.indx, changed.uv); } else if (changed.type == 2) { op[changed.indx] = changed.uv; } else if (changed.type == 3) { op[changed.indx] = changed.uv; } else if (changed.type == 10) { op.erase(op.begin() + changed.indx2); op.insert(op.begin() + changed.indx1, changed.uv); } score = changed.pre_score; } }; // TIME_LIMIT: ms State run(const double TIME_LIMIT) { titan23::Timer sa_timer; double START_TEMP = 0.0001; double END_TEMP = 0.00001; double TEMP_VAL = (START_TEMP - END_TEMP) / TIME_LIMIT; auto make_ans_init = [&] () -> State { State state; ll a[N], b[N]; memcpy(a, A, N * sizeof(ll)); memcpy(b, B, N * sizeof(ll)); rep(op_indx, 40) { if (op_indx % 2 == 0) { // to 0; vector delta(N, INF); ll mn = INF; for (int i = 1; i < N; ++i) { delta[i] = abs(VAL-(a[0]+a[i])/2) + abs(VAL-(b[0]+b[i])/2); if (delta[i] < mn) mn = delta[i]; } for (int i = 1; i < N; ++i) { if (delta[i] == mn) { state.op.emplace_back(0, i); break; } } } else { pair ans; ll best = INF; for (int i = 1; i < N; ++i) { for (int j = i+1; j < N; ++j) { ll this_s = abs(VAL - (a[0] + (a[i]+a[j])/2) / 2) + abs(VAL - (b[0] + (b[i]+b[j])/2) / 2); if (this_s < best) { best = this_s; ans = {i, j}; } } } state.op.push_back(ans); } } state.calc_score(); 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); } } 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() << '\n'; for (auto &[u, v]: ans.op) { cout << u+1 << ' ' << v+1 << '\n'; } } int main() { ios::sync_with_stdio(false); cin.tie(0); solve(); return 0; }