namespace atcoder {} #ifdef LOCAL #define dbg(x) cerr << __LINE__ << " : " << #x << " = " << (x) << endl; #else #define NDEBUG #define dbg(x) true; #pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #endif #ifdef GTEST #include #endif #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #ifdef PERF #include #endif using namespace std; using namespace atcoder; #define fast_io \ ios_base::sync_with_stdio(false); \ cin.tie(0); \ cout.tie(0); #define ll long long int #define rep(i, n) for (int i = 0; i < (int)(n); i++) #define reps(i, n) for (int i = 1; i <= (int)(n); i++) #define REP(i, n) for (int i = n - 1; i >= 0; i--) #define REPS(i, n) for (int i = n; i > 0; i--) #define MOD (long long int)(1e9 + 7) #define INF (int)(1e9) #define LINF (long long int)(1e18) #define chmax(a, b) a = (((a) < (b)) ? (b) : (a)) #define chmin(a, b) a = (((a) > (b)) ? (b) : (a)) #define ALL(v) v.begin(), v.end() typedef pair Pii; typedef pair Pll; constexpr double PI = acos(-1); #ifdef NDEBUG #define CHECK(v1, op, v2) #else #define CHECK(v1, op, v2) \ if (!((v1)op(v2))) { \ cerr << "ERROR:" << (v1) << " " << (v2) << endl; \ assert((v1)op(v2)); \ } #endif long double nCr(const int n, const int r) { long double ret = 1; rep(t, r) { ret *= (n - t); ret /= (r - t); } return ret; } template string to_string(const vector& vec) { string ret = ""; rep(i, vec.size()) { ret += vec[i].to_string(); if (i + 1 != vec.size()) { ret += ","; } } return ret; } template ostream& operator<<(ostream& os, const vector& vec) { os << to_string(vec); return os; } uint32_t xorshift() { static uint32_t x = 12345789; static uint32_t y = 362436069; static uint32_t z = 521288629; static uint32_t w = 88675123; uint32_t t; t = x ^ (x << 11); x = y; y = z; z = w; w ^= t ^ (t >> 8) ^ (w >> 19); return w; } int rand(const uint32_t l, const uint32_t r) { return xorshift() % (r - l) + l; } uint32_t rand_other_than(const uint32_t l, const uint32_t r, const uint32_t other) { const uint32_t num = rand(l, r - 1); return num + (num >= other); } template const T& rand_vec(const vector& vec) { assert(vec.size() > 0); return vec[rand(0, vec.size())]; } template void shuffle(vector& vec) { rep(l, (int)vec.size() - 1) { const int idx = rand(l, vec.size()); swap(vec[idx], vec[l]); } } class Timer { chrono::system_clock::time_point _start, _end; ll _sum = 0, _count = 0; public: void start() { _start = chrono::system_clock::now(); } void stop() { _end = chrono::system_clock::now(); } void add() { const chrono::system_clock::time_point now = chrono::system_clock::now(); _sum += static_cast( chrono::duration_cast(now - _start).count()); _count++; } ll sum() const { return _sum / 1000; } int count() const { return _count; } string average() const { if (_count == 0) { return "NaN"; } return to_string(_sum / 1000 / _count); } void reset() { _start = chrono::system_clock::now(); _sum = 0; _count = 0; } inline int ms() const { const chrono::system_clock::time_point now = chrono::system_clock::now(); return static_cast( chrono::duration_cast(now - _start).count() / 1000); } inline int ns() const { const chrono::system_clock::time_point now = chrono::system_clock::now(); return static_cast( chrono::duration_cast(now - _start).count()); } }; #ifdef LOCAL struct Timers : unordered_map { friend ostream& operator<<(ostream& os, const Timers& timers) { for (const auto& pa : timers) { os << pa.first << " time: " << pa.second.sum() / 1000 << " count: " << pa.second.count() << endl; } return os; } }; #else struct Timers { struct Dummy { void start() const {} void add() const {} }; Dummy dummy; const Dummy& operator[](const std::string& str) { return dummy; } friend ostream& operator<<(ostream& os, const Timers& timers) { return os; } }; #endif Timers global_timers; /* start */ Timer global_timer; int N; vector A,B; constexpr ll base = 5 * (ll)(1e17); int query = 50; vector> ans; pair Mean(const int i, const int j){ const ll a = (A[i] + A[j])/2; const ll b = (B[i] + B[j])/2; return {a,b}; } ll Cost(const ll a, const ll b){ return max(abs(a-base), abs(b-base)); } void Do(const int i, const int j){ assert(query >= 0); assert(i!=j); query--; const auto [a,b] = Mean(i,j); A[i] = A[j] = a; B[i] = B[j] = b; ans.push_back({i,j}); } void PrintAns(const vector>& vec){ cout << vec.size()<>N; A.resize(N); B.resize(N); rep(i,N){ cin>>A[i]>>B[i]; } cerr<<"score: " << "1"< PARAMS = {1.0, 0.1}; /* start */ class Solver { public: Solver() {} void Solve() { // baseに近いやつを1個作る // 貪欲 pair best; ll minEval = LINF; rep(i,N){ rep(j,i){ const auto [a,b] = Mean(i,j); const auto cost = Cost(a,b); if(cost < minEval){ minEval = cost; best = {i,j}; } } } Do(best.first, best.second); // 1を殴る while(query > 0){ int best_j = -1; ll minEval = LINF; rep(j, N){ if(j != 0){ const auto [a,b] = Mean(0,j); const auto cost = Cost(a,b); if(cost < minEval){ minEval = cost; best_j = j; } }else{ const auto cost = Cost(A[0],B[0]); if(cost < minEval){ minEval = cost; best_j = j; } } } if(best_j == 0) break; Do(0, best_j); } PrintAns(ans); return; } private: }; int main(int argc, char* argv[]) { fast_io; if (argc >= 2) { int idx = 0; for (int i = 1; i < argc; ++i) { PARAMS[idx++] = std::stod(argv[i]); } } Timer timer; timer.start(); Output::StaticInit(cin); Solver solver; solver.Solve(); return 0; }