#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; 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; } class TimeKeeper { private: std::chrono::high_resolution_clock::time_point start_time_; int64_t time_threshold_; public: TimeKeeper(const int64_t& time_threshold) : start_time_(std::chrono::high_resolution_clock::now()), time_threshold_(time_threshold) {} bool isTimeOver() const { using std::chrono::duration_cast; using std::chrono::milliseconds; auto diff = std::chrono::high_resolution_clock::now() - this->start_time_; return duration_cast(diff).count() >= time_threshold_; } }; int used[55][55]; // グローバル変数 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() { rep(i,20) { int idx1 = randint(0,n-2); int idx2 = randint(0,n-1); if (idx1 == idx2) idx1++; ans.push_back(Output(idx1+1,idx2+1)); ll va = (a[idx1]+a[idx2])/2; ll vb = (b[idx1]+b[idx2])/2; a[idx1] = a[idx2] = va; b[idx1] = b[idx2] = vb; } vector

p; rep(i,20) { 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; p.push_back(P(best_j,best_k)); used[best_j][best_k] = 1; } for (auto v : p) used[v.first][v.second] = 0; rep(i,5) { 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; } } 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() { TimeKeeper timer(950); State state; state.gready(); state.calc_score(); ll score = state.calc_score(); ll best_score = score; auto best_state = state; int iter_count = 0; while (!timer.isTimeOver()) { iter_count++; State next_state; next_state.gready(); next_state.calc_score(); ll next_score = next_state.calc_score(); if (next_score > best_score) { best_score = next_score; best_state = state; cerr << "best score: " << best_score << endl; } } best_state.print_ans(); cerr << "best_score:" << "\t" << best_score << endl; cerr << "iter_count:" << "\t" << iter_count << endl; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); read_input(); simulatedAnnealing(); return 0; }