#include #include using namespace std; using namespace chrono; #if __has_include() #include using namespace atcoder; #endif int main() { const auto start = steady_clock::now(); std::cin.tie(nullptr); std::ios_base::sync_with_stdio(false); int64_t n; cin >> n; vector as(n), bs(n); for (int64_t i = 0; i < n; i++) { cin >> as[i] >> bs[i]; } random_device rnd; mt19937 engine(rnd()); uniform_int_distribution<> randn(0, n - 1); uniform_int_distribution<> rand1n(1, n - 1); int64_t c = 500000000000000000LL; auto calc_score = [&] { return int64_t(2000000 - 100000 * log10(max(abs(as[0] - c), abs(bs[0] - c)) + 1)); }; auto f = [&](int64_t a, int64_t b) { return max(abs(a - c), abs(b - c)); }; pair p = {2 * c - as[0], 2 * c - bs[0]}; int64_t s = numeric_limits::max(); vector xs; while (duration_cast(steady_clock::now() - start).count() < 900) { int64_t sz = rand1n(engine); vector ys(sz); ys[0] = rand1n(engine); for (int64_t i = 1; i < sz; i++) { ys[i] = rand1n(engine); } vector cs(as), ds(bs); for (int64_t i = 1; i < ys.size(); i++) { int64_t x = (cs[ys[i - 1]] + cs[ys[i]]) / 2; int64_t y = (ds[ys[i - 1]] + ds[ys[i]]) / 2; cs[ys[i - 1]] = cs[ys[i]] = x; ds[ys[i - 1]] = ds[ys[i]] = y; } int64_t i = [&] { int64_t ret = 1; for (int64_t i = 2; i < n; i++) { int64_t x = (cs[0] + cs[i]) / 2; int64_t y = (ds[0] + ds[i]) / 2; int64_t a = (cs[0] + cs[ret]) / 2; int64_t b = (ds[0] + ds[ret]) / 2; if (f(x, y) < f(a, b)) { ret = i; } } return ret; }(); cs[0] = (cs[0] + cs[i]) / 2; ds[0] = (ds[0] + ds[i]) / 2; if (f(cs[0], ds[0]) < s) { s = f(cs[0], ds[0]); xs = ys; } } vector us, vs; for (int64_t i = 1; i < xs.size(); i++) { us.push_back(xs[i - 1] + 1); vs.push_back(xs[i] + 1); } us.push_back(1); vs.push_back([&] { int64_t ret = 1; for (int64_t i = 2; i < n; i++) { int64_t x = (as[0] + as[i]) / 2; int64_t y = (bs[0] + bs[i]) / 2; int64_t a = (as[0] + as[ret]) / 2; int64_t b = (bs[0] + bs[ret]) / 2; if (f(x, y) < f(a, b)) { ret = i; } } ret++; return ret; }()); cout << us.size() << '\n'; for (int64_t i = 0; i < us.size(); i++) { cout << us[i] << ' ' << vs[i] << '\n'; } // for (int64_t i = 0; i < us.size(); i++) { // int64_t x = (as[us[i] - 1] + as[vs[i] - 1]) / 2; // int64_t y = (bs[us[i] - 1] + bs[vs[i] - 1]) / 2; // as[us[i] - 1] = as[vs[i] - 1] = x; // bs[us[i] - 1] = bs[vs[i] - 1] = y; // } // cerr << calc_score() << endl; // for (int64_t i = 0; i < n; i++) { // cerr << i << ' ' << as[i] << ' ' << bs[i] << endl; // } return 0; }