#pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #ifdef ONLINE_JUDGE // #define NDEBUG #endif // ONLINE_JUDGE #include #include #ifndef ONLINE_JUDGE #include #endif // ONLINE_JUDGE using namespace std; using namespace atcoder; #define ll long long int #define ull unsigned long long int template inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; } template inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; } class Xorshift { public: explicit Xorshift(uint32_t seed): x_(seed) { assert(seed); } // [0, stop) uint32_t randrange(uint32_t stop) { assert(stop > 0); next(); return x_ % stop; } // [start, stop) uint32_t randrange(uint32_t start, uint32_t stop) { assert(start < stop); next(); return start + x_ % (stop - start); } // [a, b] uint32_t randint(uint32_t a, uint32_t b) { assert(a <= b); return randrange(a, b + 1); } // [0.0, 1.0] double random() { next(); return static_cast(x_) * (1.0 / static_cast(UINT32_MAX)); } // [a, b] or [b, a] double uniform(double a, double b) { return a + (b - a) * random(); } private: uint32_t x_; void next() { x_ ^= x_ << 13; x_ ^= x_ >> 17; x_ ^= x_ << 5; } }; class IndexSet { public: explicit IndexSet(int n): n_(n), positions_(n, -1) {} void insert(int x) { assert(0 <= x && x < n_); assert(!contains(x)); positions_[x] = data_.size(); data_.push_back(x); } void erase(int x) { assert(0 <= x && x < n_); assert(contains(x)); int i = positions_[x]; int y = data_.back(); data_[i] = y; data_.pop_back(); positions_[y] = i; positions_[x] = -1; } bool contains(int x) const { assert(0 <= x && x < n_); return positions_[x] != -1; } int choice(Xorshift& rng) const { assert(!data_.empty()); return data_[rng.randrange(data_.size())]; } const vector& get_data() const { return data_; } size_t size() const { return data_.size(); } void clear() { for (int x : data_) { positions_[x] = -1; } data_.clear(); } private: int n_; vector data_; vector positions_; }; class Timer { public: explicit Timer() { begin(); elapsed_time_ = 0.0; } void begin() { start_time_ = chrono::system_clock::now(); } double get_time() { chrono::system_clock::time_point end_time = chrono::system_clock::now(); elapsed_time_ = chrono::duration_cast(end_time - start_time_).count(); elapsed_time_ *= 1e-9; // from nanoseconds to seconds return elapsed_time_; } double get_last_time() const { return elapsed_time_; } bool yet(double time_limit) { return get_time() < time_limit; } private: chrono::system_clock::time_point start_time_; double elapsed_time_; }; constexpr int sa_time_counts = 1 << 4; constexpr size_t sa_random_steps = 1ul << 12; class SimulatedAnnealing { public: explicit SimulatedAnnealing(double t_first, double t_last, bool exponential, double time_limit, uint_fast32_t seed) : t_first_(t_first), t_last_(t_last), exponential_(exponential), time_limit_(time_limit) { assert(0.0 <= t_last_ && t_last_ <= t_first_); time_counter_ = sa_time_counts; temperature_ = t_first_; log2_random_index_ = 0; for (size_t i = 0; i < sa_random_steps; ++i) { log2_random_[i] = log2(static_cast(i + 1) / static_cast(sa_random_steps)); } mt19937 rng(seed); shuffle(log2_random_.begin(), log2_random_.end(), rng); } template bool accept(T profit, const Timer& timer) { if (profit >= static_cast(0)) { return true; } else { return static_cast(profit) > get_threshold(timer); } } double get_threshold(const Timer& timer) { update_temperature(timer); ++log2_random_index_; log2_random_index_ &= (sa_random_steps - 1ul); return temperature_ * log2_random_[log2_random_index_]; } private: double t_first_, t_last_; bool exponential_; double time_limit_; int time_counter_; double temperature_; size_t log2_random_index_; array log2_random_; void update_temperature(const Timer& timer) { if (time_counter_-- == 0) { time_counter_ = sa_time_counts; double progress = timer.get_last_time() / time_limit_; if (exponential_) { temperature_ = pow(t_first_, 1.0 - progress) * pow(t_last_, progress); } else { temperature_ = t_first_ * (1.0 - progress) + t_last_ * progress; } } } }; constexpr double time_limit = 0.95; constexpr int n = 45; constexpr int max_turn = 50; constexpr ll goal = 5e17; constexpr ll sum_goal = 1e18; struct Input { array,n> cards; void input() { int _n; cin >> _n; assert(_n == n); for (int i = 0; i < n; ++i) { cin >> cards[i].first >> cards[i].second; } } void input(const string& filename) { ifstream in(filename); assert(in); int _n; in >> _n; assert(_n == n); for (int i = 0; i < n; ++i) { in >> cards[i].first >> cards[i].second; } } }; constexpr double t0 = 0.5; constexpr double t1 = 0.1; struct Solver { Timer timer; Xorshift rng; const Input input; vector> best_ans; ll min_cost; Solver(const Input& input): rng(1), input(input) {} vector> init_ans() { vector> ans(max_turn); array,n> cards = input.cards; for (int turn = 0; turn < max_turn; ++turn) { int best_u = -1; int best_v = -1; double max_profit = -numeric_limits::infinity(); for (int u = 0; u < n; ++u) { auto [ux, uy] = cards[u]; for (int v = u + 1; v < n; ++v) { auto [vx, vy] = cards[v]; double profit = log(abs(ux - goal) + abs(uy - goal) + 1) + log(abs(vx - goal) + abs(vy - goal) + 1); profit -= 2 * log(abs((ux + vx) / 2 - goal) + abs((uy + vy) / 2 - goal) + 1); if (chmax(max_profit, profit)) { best_u = u; best_v = v; } } if (turn == 0) { break; } } auto [ux, uy] = cards[best_u]; auto [vx, vy] = cards[best_v]; cards[best_u].first = cards[best_v].first = (ux + vx) / 2; cards[best_u].second = cards[best_v].second = (uy + vy) / 2; ans[turn] = {best_u, best_v}; } return ans; } bool choose_first(int turn) { return (int)rng.randrange(max_turn) < turn; } ll calc_cost(const vector>& ans) { array,n> cards = input.cards; for (auto [u, v] : ans) { ll a = (cards[u].first + cards[v].first) / 2; ll b = (cards[u].second + cards[v].second) / 2; cards[u] = {a, b}; cards[v] = {a, b}; } return max(abs(cards[0].first - goal), abs(cards[0].second - goal)); } void solve() { SimulatedAnnealing sa(t0, t1, false, time_limit, 0); vector> ans = init_ans(); ll cost = calc_cost(ans); best_ans = ans; min_cost = cost; while (timer.yet(time_limit)) { int turn = rng.randrange(20, ans.size()); auto [a, b] = ans[turn]; int u = choose_first(turn) ? 0 : rng.randrange(1, n); int v = rng.randrange(n - 1); if (v >= u) { ++v; } ans[turn] = {u, v}; ll new_cost = calc_cost(ans); if (new_cost < cost || sa.accept(log2(cost) - log2(new_cost), timer)) { cost = new_cost; if (chmin(min_cost, cost)) { best_ans = ans; } } else { ans[turn] = {a, b}; } } } void print() const { cout << best_ans.size() << "\n"; for (auto [u, v] : best_ans) { cout << u + 1 << " " << v + 1 << "\n"; } } void print(const string& filename) const { ofstream out(filename); assert(out); out << best_ans.size() << "\n"; for (auto [u, v] : best_ans) { out << u + 1 << " " << v + 1 << "\n"; } } ll score() const { return 2000000 - 100000 * log10(min_cost + 1); } }; void multi_test(int cases, int num_threads) { if (cases <= 0) { return; } cerr << "cases: " << cases << endl; vector scores(cases); vector times(cases); #ifndef ONLINE_JUDGE omp_set_num_threads(num_threads); #pragma omp parallel for #endif // ONLINE_JUDGE for (int seed = 0; seed < cases; ++seed) { string filename = to_string(seed + 1); filename = "in/in" + string(3 - filename.size(), '0') + filename + ".txt"; Input input; input.input(filename); Solver solver(input); solver.solve(); times[seed] = solver.timer.get_time(); scores[seed] = solver.score(); cerr << filename << " " << scores[seed] << " " << times[seed] << " sec" << endl; solver.print("out" + filename.substr(2)); } cerr << "Average Score: " << accumulate(scores.begin(), scores.end(), 0ll) / cases << endl; cerr << "Max Time: " << *max_element(times.begin(), times.end()) << " sec" << endl; cerr << "Average Time: " << accumulate(times.begin(), times.end(), 0.0) / cases << " sec" << endl; } int main() { ios::sync_with_stdio(false); std::cin.tie(nullptr); Input input; input.input(); Solver solver(input); solver.solve(); solver.print(); #ifndef ONLINE_JUDGE cerr << "Score = " << solver.score() << ", " << solver.timer.get_time() << " sec" << endl; int cases = 50; int num_threads = 10; multi_test(cases, num_threads); #endif // ONLINE_JUDGE return 0; }