#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 const int BEAMWIDTH = 6000; vector > beam(N - 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 - 3; level++) { double mul = pow(0.5, level != N - 3 ? level + 2 : N - 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)); } } sort(beam[level].begin(), beam[level].end()); if (int(beam[level].size()) > BEAMWIDTH) { beam[level].resize(BEAMWIDTH); } cerr << "level = " << level << ": size = " << beam[level].size() << ", score = " << beam[level][0].score() << endl; } // step #3. reconstruction int pos = 0; vector track; for (int level = N - 3; level >= 1; level--) { uint64_t b = beam[level][pos].bit; pos = beam[level][pos].pre; track.push_back(b); } track.push_back(beam[0][pos].bit); vector ord; for (int i = 0; i < N - 3; i++) { uint64_t b = track[i] ^ track[i + 1]; int pos = __builtin_ctzll(b); ord.push_back(pos); } for (int i = N - 1; i >= 0; i--) { if (!((track[N - 3] >> i) & 1)) { ord.push_back(i); } } cout << N - 1 << endl; for (int i = 0; i < N - 3; i++) { cout << ord[i] + 1 << ' ' << ord[i + 1] + 1 << endl; } cout << ord[N - 2] + 1 << ' ' << ord[N - 1] + 1 << endl; cout << ord[N - 3] + 1 << ' ' << ord[N - 1] + 1 << endl; return 0; }