#include #include #include #include #include using namespace std; const long long Target = 500000000000000000LL; void Operation(vector& A, vector& B, int idx1, int idx2) { long long avg1 = (A[idx1] + A[idx2]) / 2LL; long long avg2 = (B[idx1] + B[idx2]) / 2LL; A[idx1] = avg1; B[idx1] = avg2; A[idx2] = avg1; B[idx2] = avg2; } double GetScore(vector P, long long Target, vector Depth) { vector Vec(P.size(), 0); bool flag = false; for (int i = 0; i < Vec.size(); i++) { int idx = (Depth[i] >= 1 ? Depth[i] + 1 : (flag == true ? 1 : 0)); Vec[idx] = P[i]; if (idx == 0) flag = true; } double Sum = (double)Target * (double)(1LL << (P.size() - 1)); for (int i = Vec.size() - 1; i >= 0; i--) { Sum -= (double)Vec[i] * (double)(1LL << max(0, i - 1)); } return abs(Sum); } int main() { srand((unsigned)time(NULL)); // Step 1. 入力 vector A(50, 0); vector B(50, 0); long long N; cin >> N; for (int i = 0; i < N; i++) cin >> A[i] >> B[i]; // Step 2. 最初のステップ long long MinV = (1LL << 60); long long MinID = -1; for (int i = 1; i < N; i++) { long long v1 = (A[0] + A[i]) / 2LL; long long v2 = (B[0] + B[i]) / 2LL; long long err = max(abs(v1 - Target), abs(v2 - Target)); if (MinV > err) { MinV = err; MinID = i; } } Operation(A, B, 0, MinID); // Step 3. ランダム貪欲 vector MinOrder; int StartTime = clock(); long long RecordScore = Target; while (clock() - StartTime < 5 * CLOCKS_PER_SEC / 10) { vector C = A; vector D = B; long long RemainC = Target * 2 - C[0]; long long RemainD = Target * 2 - D[0]; vector Used(N, false); vector Order; Order.push_back(0); // 貪欲法スタート int param1 = rand() % 3 + 2; int param2 = rand() % 3 + 2; int param3 = rand() % 7; while (true) { vector> Vec; for (int i = 1; i < N; i++) { if (Used[i] == true) continue; long long v1 = abs(RemainC - C[i]); if (v1 >= RemainC) continue; long long v2 = abs(RemainD - D[i]); if (v2 >= RemainD) continue; double keisuu = 1.0 - 0.1 * param3 * max(abs(C[i] - Target), abs(D[i] - Target)) / Target; Vec.push_back(make_pair(max(v1, v2) * keisuu, i)); } sort(Vec.begin(), Vec.end()); if (Vec.size() == 0) break; int idx = Vec[rand() % max(1, min(param1, (int)Vec.size() / param2))].second; RemainC = min(6LL * Target, 2LL * RemainC - C[idx]); RemainD = min(6LL * Target, 2LL * RemainD - D[idx]); Order.push_back(idx); Used[idx] = true; } for (int i = 1; i < N; i++) { if (Used[i] == false) Order.push_back(i); } // スコアを出す vector> CurrentAns; CurrentAns.push_back(make_pair(0, MinID)); for (int i = N - 2; i >= 0; i--) { CurrentAns.push_back(make_pair(Order[i], Order[i + 1])); Operation(C, D, Order[i], Order[i + 1]); } // スコアを比較 long long CandScore = max(abs(Target - C[0]), abs(Target - D[0])); if (RecordScore > CandScore) { RecordScore = CandScore; MinOrder = Order; } } // Step 4. 焼きなまし法 vector Depth(N, 0); for (int i = 0; i < MinOrder.size(); i++) { Depth[MinOrder[i]] = max(0, (int)MinOrder.size() - 2 - i); } vector BstDepth = Depth; double BstScore = max(GetScore(A, Target, Depth), GetScore(B, Target, Depth)); double CurScore = max(GetScore(A, Target, Depth), GetScore(B, Target, Depth)); double IniScore = CurScore; int StartTime2 = clock(); while (true) { int idx1 = rand() % Depth.size(); int idx2 = rand() % Depth.size(); if (Depth[idx1] >= 10 || Depth[idx2] >= 10 || abs(Depth[idx1] - Depth[idx2]) >= 3) continue; swap(Depth[idx1], Depth[idx2]); double CandScore = max(GetScore(A, Target, Depth), GetScore(B, Target, Depth)); if (CurScore >= CandScore || CandScore < 4.0e19) { CurScore = CandScore; if (BstScore > CandScore) { BstScore = CandScore; BstDepth = Depth; } } else { swap(Depth[idx1], Depth[idx2]); } if (clock() - StartTime2 >= 4 * CLOCKS_PER_SEC / 10) break; } // Step 5. 答えを求める vector AnsList(N, 0); bool flag = false; vector> Answer; for (int i = 0; i < N; i++) { if (flag == false && BstDepth[i] == 0) { flag = true; AnsList[0] = i; } else AnsList[BstDepth[i] + 1] = i; } Answer.push_back(make_pair(0, MinID)); for (int i = 0; i < N - 1; i++) Answer.push_back(make_pair(AnsList[i], AnsList[i + 1])); for (int i = 0; i < N - 1; i++) Operation(A, B, AnsList[i], AnsList[i + 1]); // Step 6. 出力 cout << Answer.size() << endl; for (int i = 0; i < Answer.size(); i++) cout << Answer[i].first + 1 << " " << Answer[i].second + 1 << endl; return 0; }