#include using namespace std; class state { public: double x, y; uint64_t bit; int pre; state() : x(0.0), y(0.0), bit(0), pre(-1) {} state(double x_, double y_, uint64_t bit_, int pre_) : x(x_), y(y_), bit(bit_), pre(pre_) {} double score() const { return max(abs(x), abs(y)); } bool operator<(const state& s) const { return score() < s.score(); } }; int main() { // step #1. input int N; cin >> N; vector A(N), B(N); for (int i = 0; i < N; i++) { cin >> A[i] >> B[i]; A[i] -= 5.0e+17; B[i] -= 5.0e+17; } // step #2. beam search constexpr int BEAMWIDTH = 15000; constexpr int REMAINS = 6; vector > beam(N - REMAINS - 2); for (int v1 = 1; v1 < N; v1++) { for (int v2 = v1 + 1; v2 < N; v2++) { double x = (A[0] + A[v1] + A[v2]) / 4; double y = (B[0] + B[v1] + B[v2]) / 4; uint64_t bit = ((1ULL << N) - 1) ^ (1ULL << 0) ^ (1ULL << v1) ^ (1ULL << v2); beam[0].push_back(state(x, y, bit, -1)); } } sort(beam[0].begin(), beam[0].end()); if (int(beam[0].size()) > BEAMWIDTH) { beam[0].resize(BEAMWIDTH); } for (int level = 1; level <= N - REMAINS - 3; level++) { double mul = pow(0.5, level + 2); for (int i = 0; i < int(beam[level - 1].size()); i++) { state s = beam[level - 1][i]; uint64_t b = s.bit; while (b != 0) { int pos = __builtin_ctzll(b); b ^= 1ULL << pos; double x = s.x + A[pos] * mul; double y = s.y + B[pos] * mul; uint64_t bit = s.bit ^ (1ULL << pos); beam[level].push_back(state(x, y, bit, i)); } } if (int(beam[level].size()) > BEAMWIDTH) { nth_element(beam[level].begin(), beam[level].begin() + BEAMWIDTH, beam[level].end()); beam[level].resize(BEAMWIDTH); } // cerr << "level = " << level << ": size = " << beam[level].size() << ", score = " << beam[level][0].score() << ", back = " << beam[level].back().score() << endl; } // step #3. enumerate all remaining combinations vector > weights; vector path; auto dfs = [&](auto& self, int depth, int rem, int val) -> void { if (rem < val) { return; } if (val == 0) { array v; for (int i = 0; i < REMAINS; i++) { v[i] = (i < int(path.size()) ? pow(2.0, -((N - REMAINS - 1) + path[i])) : 0.0); } reverse(v.begin(), v.end()); do { weights.push_back(v); } while (next_permutation(v.begin(), v.end())); return; } for (int i = 0; i <= rem && i <= val; i++) { self(self, depth + 1, rem - i, (val - i) * 2); path.push_back(depth); } while (!path.empty() && path.back() == depth) { path.pop_back(); } }; dfs(dfs, 0, REMAINS, 1); const int SUBSTATES = weights.size(); cerr << "substates = " << SUBSTATES << endl; // step #4. brute force double bestscore = 1.0e+99; vector bestdepth; for (int i = 0; i < int(beam[N - REMAINS - 3].size()); i++) { state s = beam[N - REMAINS - 3][i]; uint64_t rembit = s.bit; array subidx; array suba, subb; for (int j = 0; j < REMAINS; j++) { subidx[j] = __builtin_ctzll(rembit); suba[j] = A[subidx[j]]; subb[j] = B[subidx[j]]; rembit ^= 1ULL << subidx[j]; } for (int j = 0; j < SUBSTATES; j++) { double x = s.x, y = s.y; for (int k = 0; k < REMAINS; k++) { x += suba[k] * weights[j][k]; y += subb[k] * weights[j][k]; } double score = max(abs(x), abs(y)); if (bestscore > score) { // reconstruction vector depth(N, -1); for (int k = 0; k < REMAINS; k++) { if (weights[j][k] != 0.0) { depth[subidx[k]] = int(-log2(weights[j][k]) + 0.5); } } int idx = i; uint64_t prebit = s.bit; for (int k = N - REMAINS - 3; k >= 0; k--) { uint64_t nxtbit = (k != 0 ? beam[k - 1][beam[k][idx].pre].bit : (1ULL << N) - 1); uint64_t bitdiff = prebit ^ nxtbit; while (bitdiff != 0) { int pos = __builtin_ctzll(bitdiff); depth[pos] = k + 2; bitdiff ^= 1ULL << pos; } prebit = nxtbit; if (k != 0) { idx = beam[k][idx].pre; } } bestscore = score; bestdepth = depth; } } } cerr << "bestscore = " << bestscore << endl; // step #5. construction vector > answer; vector curdepth = bestdepth; while (curdepth[0] != 0) { int p1 = max_element(curdepth.begin(), curdepth.end()) - curdepth.begin(); int p2 = max_element(curdepth.begin() + p1 + 1, curdepth.end()) - curdepth.begin(); answer.push_back({p1, p2}); curdepth[p1] -= 1; curdepth[p2] = -1; } // step #6. output cout << answer.size() << endl; for (array v : answer) { cout << v[0] + 1 << ' ' << v[1] + 1 << endl; } return 0; }