#include using namespace std; // #include // using namespace atcoder; #pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #define rep(i,n) for(int i = 0; i < (n); ++i) #define drep(i,n) for(int i = (n)-1; i >= 0; --i) #define rng(a) a.begin(),a.end() #define rrng(a) a.rbegin(),a.rend() template using vc = vector; template using vv = vc>; template using PQ = priority_queue,greater >; templatevoid uni(T& a){sort(rng(a));a.erase(unique(rng(a)),a.end());} using ll = long long; using P = pair; int dx[4] = {-1,0,1,0}; int dy[4] = {0,-1,0,1}; constexpr int INF = 1001001001; constexpr ll INFL = 1001002003004005006ll; /* mst で各放送局を連結にする 差分更新しない焼きなまし 近傍:放送局をひとつ選び出力を変更する */ inline unsigned long long xor128() { static unsigned long long rx = 123456789, ry = 986960440, rz = 738905609, rw = 23140692; unsigned long long rt = (rx ^ (rx << 11)); rx = ry;ry = rz;rz = rw; return (rw = (rw ^ (rw >> 19)) ^ (rt ^ (rt >> 8))); } inline float rand128(float min = 0, float max = 1){ return (float)(xor128() % 0xFFFF) / 0xFFFF * (max - min) + min; } inline unsigned long long randint(int min, int max){ return xor128()%(max - min + 1) + min; } struct Timer { double t = 0.0; double lastStop = 0.0; bool stopped = false; Timer() { restart(); } inline void restart() { t = now(); stopped = false; } inline double time() { if (stopped) return lastStop - t; else return now() - t; } inline double now() { unsigned long long l, h; __asm__ ("rdtsc" : "=a"(l), "=d"(h)); return (double)(l | h << 32) * 3.333333333333333e-10; } }; // グローバル変数 Timer timer; int n; // 頂点数 vector ga; vector gb; void read_input() { cin >> n; ga.resize(n); gb.resize(n); rep(i,n) cin >> ga[i] >> gb[i]; } struct Output { int u,v; Output (int u=0, int v=0) : u(u), v(v) {} }; struct State { vector a; vector b; vector ans; State() { a.resize(n); b.resize(n); a = ga; b = gb; } void init() { } void make_init_ans() { rep(i,50) { int idx1 = randint(0,n-2); int idx2 = randint(0,n-1); if (idx1 == idx2) idx1++; ans.push_back(Output(idx1,idx2)); ll va = (a[idx1]+a[idx2])/2; ll vb = (b[idx1]+b[idx2])/2; a[idx1] = a[idx2] = va; b[idx1] = b[idx2] = vb; } } void print_ans() { cout << ans.size() << endl; for (Output o : ans) { cout << o.u << " " << o.v << endl; } } void gready() { set

st; rep(i,40) { ll v1 = abs(5e17-a[0]); ll v2 = abs(5e17-b[0]); ll best_score = INFL; int best_j = -1; int best_k = -1; for (int j=0; j score) { best_score = score; best_j = j; best_k = k; } } } if (best_j == -1) continue; ans.push_back(Output(best_j+1,best_k+1)); ll va = (a[best_k]+a[best_j])/2; ll vb = (b[best_k]+b[best_j])/2; a[best_k] = a[best_j] = va; b[best_k] = b[best_j] = vb; st.insert(P(best_j,best_k)); // cerr << "--------------- " << best_j << " " << best_k << endl; // rep(j,n) cerr << j << " " << a[j] << " " << b[j] << endl; // cerr << "--------------- " << endl; } rep(i,10) { ll v1 = abs(5e17-a[0]); ll v2 = abs(5e17-b[0]); ll best_score = INFL; int best_j = -1; for (int j=1; j score) { best_score = score; best_j = j; } } if (best_j == -1) continue; ans.push_back(Output(1,best_j+1)); ll va = (a[0]+a[best_j])/2; ll vb = (b[0]+b[best_j])/2; a[0] = a[best_j] = va; b[0] = b[best_j] = vb; // cerr << "--------------- " << endl; // rep(j,n) cerr << j << " " << a[j] << " " << b[j] << endl; // cerr << "--------------- " << endl; } } void show_ans() { } void transition() { int idx = randint(0,49); } void rollback() { } ll calc_score() { ll V1 = abs(a[0]-5e17); ll V2 = abs(b[0]-5e17); return 2000000 - 100000*log10(max(V1,V2)+1); } }; void simulatedAnnealing() { State state; // state.make_init_ans(); state.gready(); // state.calc_score(); state.print_ans(); ll score = state.calc_score(); // cerr << score << endl; return; ll best_score = score; double time_limit = 0.900; double start_temp = 1000.0; double end_temp = 10.0; auto best_state = state; int iter_count = 0; // while (timer.time() < time_limit) { // iter_count++; // auto next_state = state; // next_state.transition(); // next_state.calc_score(); // auto next_score = next_state.score; // // score maximumize // double temp = start_temp + (end_temp - start_temp) * timer.time() / time_limit; // double probability = exp((next_score - now_score) / temp); // bool is_force_next = probability > rand128(); // if (next_score > now_score || is_force_next) { // now_score = next_score; // state = next_state; // } // if (next_score > best_score) { // best_score = next_score; // best_state = state; // // cerr << "best score: " << best_score << endl; // } // } // cerr << "best_score:" << "\t" << best_score << endl; // cerr << "iter_count:" << "\t" << iter_count << endl; // best_state.print_ans(); } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); read_input(); simulatedAnnealing(); return 0; }