#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; } // 時間をDouble型で管理し、経過時間も取り出せるクラス class TimeKeeper { private: std::chrono::high_resolution_clock::time_point start_time_; double time_threshold_; double now_time_ = 0; public: TimeKeeper(const double time_threshold) : start_time_(std::chrono::high_resolution_clock::now()), time_threshold_(time_threshold) {} void setNowTime() { auto diff = std::chrono::high_resolution_clock::now() - this->start_time_; this->now_time_ = std::chrono::duration_cast(diff).count() * 1e-3; // ms } double getNowTime() const { return this->now_time_; } bool isTimeOver() const { return now_time_ >= 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,n) { if (i == 0) continue; int idx1 = 0; int idx2 = i; ans.push_back(Output(idx1,idx2)); } } void transition() { int m = ans.size(); int idx1 = randint(0,m-2); int idx2 = randint(0,m-1); if (idx1 == idx2) idx1++; swap(ans[idx1],ans[idx2]); } void print_ans() { cout << ans.size() << endl; for (Output o : ans) { cout << o.u << " " << o.v << endl; } } ll calc_score() { auto aa = a; auto bb = b; rep(i,ans.size()) { int idx1 = ans[i].u; int idx2 = ans[i].v; ll va = (aa[idx1]+aa[idx2])/2; ll vb = (bb[idx1]+bb[idx2])/2; aa[idx1] = aa[idx2] = va; bb[idx1] = bb[idx2] = vb; } ll V1 = abs(aa[0]-5e17); ll V2 = abs(bb[0]-5e17); return 2000000 - 100000*log10(max(V1,V2)+1); } }; void simulatedAnnealing() { TimeKeeper timer(950); State state; state.make_init_ans(); state.calc_score(); ll score = state.calc_score(); ll best_score = score; double time_limit = 950; double start_temp = 1000.0; double end_temp = 10.0; auto best_state = state; int iter_count = 0; while (true) { timer.setNowTime(); if (timer.isTimeOver()) break; iter_count++; State next_state = state; next_state.transition(); ll next_score = next_state.calc_score(); // score maximumize double temp = start_temp + (end_temp - start_temp) * timer.getNowTime() / time_limit; double probability = exp((next_score - score) / temp); bool is_force_next = probability > rand128(); if (next_score > score || is_force_next) { score = next_score; state = next_state; } if (next_score > best_score) { best_score = next_score; best_state = next_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; }