#if __INCLUDE_LEVEL__ == 0 #include __BASE_FILE__ namespace { constexpr i64 H = 500'000'000'000'000'000; struct Input { int n; int m; std::vector a; std::vector b; }; Input read_input() { Input in; scan(in.n); in.m = 50; in.a.resize(in.n); in.b.resize(in.n); for (const int i : rep(in.n)) { scan(in.a[i], in.b[i]); } return in; } double evaluate(const Input& in, const std::vector& p, const std::vector>& pre) { auto a = in.a; auto b = in.b; for (auto [i, j] : pre) { i = p[i]; j = p[j]; a[i] = a[j] = (a[i] + a[j]) >> 1; b[i] = b[j] = (b[i] + b[j]) >> 1; } i64 x = a[p.back()]; i64 y = b[p.back()]; for (const int i : p | views::reverse | views::drop(1)) { x = (x + a[i]) >> 1; y = (y + b[i]) >> 1; } return std::log1p(std::max(std::abs(x - H), std::abs(y - H))); } void answer(const std::vector& p, const std::vector>& pre) { print(len(pre) + len(p) - 1); for (const auto& [i, j] : pre) { print(p[i] + 1, p[j] + 1); } int min_i = p.back(); for (const int i : p | views::reverse | views::drop(1)) { print(min_i + 1, i + 1); chmin(min_i, i); } } void solve() { const Input in = read_input(); constexpr int S = 40; std::vector p(in.n); std::iota(p.begin(), p.end(), 0); std::vector> pre(in.m - in.n + 1); for (auto& [i, j] : pre) { do { i = randint(S, in.n - 1); j = randint(S, in.n - 1); } while (i == j); } double cur = evaluate(in, p, pre); double best = cur; auto best_p = p; auto best_pre = pre; for (const auto& sa : Sa<256>(4 << 20, 0.5, 0.4)) { if (randint(0, 9)) { const int i = randint(0, in.n - 2); std::swap(p[i], p[i + 1]); const double nxt = evaluate(in, p, pre); if (cur + sa.tol < nxt) { std::swap(p[i], p[i + 1]); } else { cur = nxt; } } else { const int i = randint(0, in.m - in.n); const auto old = pre[i]; do { pre[i].first = randint(S, in.n - 1); pre[i].second = randint(S, in.n - 1); } while (pre[i].first == pre[i].second); const double nxt = evaluate(in, p, pre); if (cur + sa.tol < nxt) { pre[i] = old; } else { cur = nxt; } } if (chmin(best, cur)) { best_p = p; best_pre = pre; } } answer(best_p, best_pre); } } // namespace int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); std::cout << std::setprecision(DBL_DECIMAL_DIG); solve(); } #else // __INCLUDE_LEVEL__ #include namespace xorshift { using u64 = std::uint64_t; using u128 = ::__uint128_t; inline u64 x = std::chrono::steady_clock::now().time_since_epoch().count(); inline u64 next() { x ^= x << 7; x ^= x >> 9; return x; } int randint(int a, int b) { const u64 m = static_cast(b) - static_cast(a) + 1; return a + static_cast(u128{next()} * m >> 64); } template void shuffle(R&& r) { const int n = static_cast(std::ranges::size(r)); if (n < 2) { return; } for (const int i : std::views::iota(1, n)) { if (const int j = randint(0, i); j < i) { std::ranges::swap(r[i], r[j]); } } } double uniform() { return static_cast(next()) / static_cast(UINT64_MAX); } double uniform(double a, double b) { return a + (b - a) * uniform(); } } // namespace xorshift using xorshift::randint; using xorshift::shuffle; using xorshift::uniform; template class Sa { public: explicit Sa(std::int64_t n_iters, double start_temp = 0, double end_temp = 0) : n_iters_(n_iters), start_temp_(start_temp), cooling_rate_(start_temp ? end_temp / start_temp : 1), iter_(0), elapsed_(0), temp_(start_temp) { assert(0 <= end_temp && end_temp <= start_temp); } Sa begin() const { return *this; } int end() const { return 0; } bool operator!=(int) const { return iter_ < n_iters_; } void operator++() { if (++iter_ % UpdateInterval == 0) { elapsed_ = static_cast(iter_) / static_cast(n_iters_); temp_ = start_temp_ * std::pow(cooling_rate_, elapsed_); } } auto operator*() const { struct { std::int64_t iter; double elapsed; double temp; double tol; } sa{iter_, elapsed_, temp_, temp_ * -std::log(uniform())}; return sa; } private: std::int64_t n_iters_; double start_temp_; double cooling_rate_; std::int64_t iter_; double elapsed_; double temp_; }; template bool chmin(T& x, U&& y) { return y < x && (x = std::forward(y), true); } template bool chmax(T& x, U&& y) { return x < y && (x = std::forward(y), true); } template T inf() { T ret; std::memset(&ret, 0x3f, sizeof(ret)); return ret; } template T inf() { return std::numeric_limits::infinity(); } template concept Range = std::ranges::range && !std::convertible_to; template concept Tuple = std::__is_tuple_like::value && !Range; namespace std { istream& operator>>(istream& is, Range auto&& r) { for (auto&& e : r) { is >> e; } return is; } istream& operator>>(istream& is, Tuple auto&& t) { return apply([&](auto&... xs) -> istream& { return (is >> ... >> xs); }, t); } ostream& operator<<(ostream& os, Range auto&& r) { for (string_view sep = ""; auto&& e : r) { os << exchange(sep, " ") << e; } return os; } ostream& operator<<(ostream& os, Tuple auto&& t) { const auto f = [&](auto&... xs) -> ostream& { [[maybe_unused]] string_view sep = ""; ((os << exchange(sep, " ") << xs), ...); return os; }; return apply(f, t); } } // namespace std void scan(auto&&... xs) { std::cin >> std::tie(xs...); } void print(auto&&... xs) { std::cout << std::tie(xs...) << '\n'; } template class fix { public: explicit fix(F f) : f_(std::move(f)) {} decltype(auto) operator()(auto&&... xs) const { return f_(std::ref(*this), std::forward(xs)...); } private: F f_; }; inline auto rep(int l, int r) { return std::views::iota(std::min(l, r), r); } inline auto rep(int n) { return rep(0, n); } inline auto rep1(int l, int r) { return rep(l, r + 1); } inline auto rep1(int n) { return rep(1, n + 1); } namespace ranges = std::ranges; namespace views = std::views; using i64 = std::int64_t; #define len(...) static_cast(ranges::size(__VA_ARGS__)) #endif // __INCLUDE_LEVEL__