#pragma GCC optimize ("O3") #pragma GCC optimize ("unroll-loops") #pragma GCC target ("avx2") #include <iostream> #include <iomanip> #include <vector> #include <algorithm> #include <utility> #include <string> #include <queue> #include <stack> #include <unordered_set> #include <random> #include <cmath> #include <cassert> #include <x86intrin.h> struct xorshift64 { unsigned long long int x = 88172645463325252ULL; inline unsigned short nextUShort() { x = x ^ (x << 7); return x = x ^ (x >> 9); } inline unsigned int nextUShortMod(unsigned long long int mod) { x = x ^ (x << 7); x = x ^ (x >> 9); return ((x & 0x0000ffffffffffff) * mod) >> 48; } inline unsigned int nextUInt() { x = x ^ (x << 7); return x = x ^ (x >> 9); } inline unsigned int nextUIntMod(unsigned long long int mod) { x = x ^ (x << 7); x = x ^ (x >> 9); return ((x & 0x00000000ffffffff) * mod) >> 32; } inline unsigned long long int nextULL() { x = x ^ (x << 7); return x = x ^ (x >> 9); } inline double nextDouble() { x = x ^ (x << 7); x = x ^ (x >> 9); return (double)x * 5.42101086242752217e-20; } }; struct timer { double t = 0.0; double lastStop = 0.0; bool stopped = false; timer() { restart(); } inline void restart() { t = now(); stopped = false; } inline void start() { if (stopped) { t += now() - lastStop; stopped = false; } } inline void stop() { if (!stopped) { lastStop = now(); stopped = true; } } inline double time() { if (stopped) return lastStop - t; else return now() - t; } inline double now() { unsigned long long l, h; __asm__ ("rdtsc" : "=a"(l), "=d"(h)); #ifdef LOCAL return (double)(l | h << 32) * 2.857142857142857e-10; // 1 / 3.5e9, for local (Ryzen 9 3950X) #else //return (double)(l | h << 32) * 3.5714285714285715e-10; // 1 / 2.8e9, for AWS EC2 C3 (Xeon E5-2680 v2) //return (double)(l | h << 32) * 3.4482758620689656e-10; // 1 / 2.9e9, for AWS EC2 C4 (Xeon E5-2666 v3) return (double)(l | h << 32) * 3.333333333333333e-10; // 1 / 3.0e9, for AWS EC2 C5 (Xeon Platinum 8124M / Xeon Platinum 8275CL) #endif } }; using namespace std; typedef long long int ll; typedef unsigned long long int ull; typedef pair<int, int> Pii; const ll mod = 1000000007; timer theTimer; xorshift64 theRandom; mt19937 theMersenne(1); // hyper parameters // enums // structs // constants constexpr int planet_num = 100; constexpr int station_num = 8; constexpr int planet_cost_factor = 5; // inputs vector<Pii> planet_pos; // outputs vector<Pii> station_pos; vector<Pii> route_info; // internals vector<vector<int> > planet_to_planet_cost; vector<vector<int> > station_to_planet_cost; vector<vector<int> > station_to_station_cost; vector<int> planet_visit_order; void receive_input() { int _n, _m; cin >> _n >> _m; planet_pos = vector<Pii>(planet_num); for (auto &planet: planet_pos) cin >> planet.first >> planet.second; } void init_planet_to_planet_cost() { planet_to_planet_cost = vector<vector<int> >(planet_num, vector<int>(planet_num)); for (int i = 0; i < planet_num; i++) { for (int j = i; j < planet_num; j++) { planet_to_planet_cost[i][j] = planet_cost_factor * planet_cost_factor * ((planet_pos[i].first - planet_pos[j].first) * (planet_pos[i].first - planet_pos[j].first) + (planet_pos[i].second - planet_pos[j].second) * (planet_pos[i].second - planet_pos[j].second)); planet_to_planet_cost[j][i] = planet_to_planet_cost[i][j]; } } } void init_station_to_planet_cost() { station_to_planet_cost = vector<vector<int> >(station_num, vector<int>(planet_num)); for (int i = 0; i < station_num; i++) { for (int j = 0; j < planet_num; j++) { station_to_planet_cost[i][j] = planet_cost_factor * ((station_pos[i].first - planet_pos[j].first) * (station_pos[i].first - planet_pos[j].first) + (station_pos[i].second - planet_pos[j].second) * (station_pos[i].second - planet_pos[j].second)); } } } void init_station_to_station_cost() { station_to_station_cost = vector<vector<int> >(station_num, vector<int>(planet_num)); for (int i = 0; i < station_num; i++) { for (int j = i; j < station_num; j++) { station_to_station_cost[i][j] = ((station_pos[i].first - station_pos[j].first) * (station_pos[i].first - station_pos[j].first) + (station_pos[i].second - station_pos[j].second) * (station_pos[i].second - station_pos[j].second)); } } } void init() { station_pos = vector<Pii>(station_num); for (int i = 0; i < station_num; i++) { station_pos[i] = Pii(theRandom.nextUIntMod(801) + 100, theRandom.nextUIntMod(801) + 100); } init_planet_to_planet_cost(); init_station_to_planet_cost(); init_station_to_station_cost(); planet_visit_order = vector<int>(planet_num + 1); { planet_visit_order[0] = 0; planet_visit_order[planet_num] = 0; int current_planet = 0; vector<bool> visited(planet_num); visited[0] = true; for (int i = 1; i < planet_num; i++) { int best_planet = -1; int best_cost = 1000000007; for (int j = 0; j < planet_num; j++) { if (!visited[j] && planet_to_planet_cost[current_planet][j] < best_cost) { best_planet = j; best_cost = planet_to_planet_cost[current_planet][j]; } } planet_visit_order[i] = best_planet; current_planet = best_planet; visited[best_planet] = true; } } } vector<Pii> find_shortest_route(int planet_from, int planet_to) { vector<bool> planet_visited(planet_num); vector<bool> station_visited(station_num); vector<Pii> planet_prev_entity(planet_num); vector<Pii> station_prev_entity(station_num); priority_queue<tuple<int, int, int, int, int>, vector<tuple<int, int, int, int, int> >, greater<tuple<int, int, int, int, int> > > que; // cost, entity_type, entity_id, prev_entity_type, prev_entity_id que.emplace(0, 1, planet_from, 1, planet_from); while (!que.empty()) { auto [cost, entity_type, entity_id, prev_entity_type, prev_entity_id] = que.top(); que.pop(); if (entity_type == 1) { // planet if (planet_visited[entity_id]) continue; planet_visited[entity_id] = true; planet_prev_entity[entity_id] = Pii(prev_entity_type, prev_entity_id); if (entity_id == planet_to) break; for (int next_planet = 0; next_planet < planet_num; next_planet++) { if (!planet_visited[next_planet]) { que.emplace(cost + planet_to_planet_cost[entity_id][next_planet], 1, next_planet, entity_type, entity_id); } } for (int next_station = 0; next_station < station_num; next_station++) { if (!station_visited[next_station]) { que.emplace(cost + station_to_planet_cost[next_station][entity_id], 2, next_station, entity_type, entity_id); } } } else if (entity_type == 2) { // station if (station_visited[entity_id]) continue; station_visited[entity_id] = true; station_prev_entity[entity_id] = Pii(prev_entity_type, prev_entity_id); for (int next_planet = 0; next_planet < planet_num; next_planet++) { if (!planet_visited[next_planet]) { que.emplace(cost + station_to_planet_cost[entity_id][next_planet], 1, next_planet, entity_type, entity_id); } } for (int next_station = 0; next_station < station_num; next_station++) { if (!station_visited[next_station]) { que.emplace(cost + station_to_station_cost[entity_id][next_station], 2, next_station, entity_type, entity_id); } } } } vector<Pii> route; int current_entity_type = 1; int current_entity_id = planet_to; while (!(current_entity_type == 1 && current_entity_id == planet_from)) { route.emplace_back(current_entity_type, current_entity_id); if (current_entity_type == 1) { // planet auto [prev_entity_type, prev_entity_id] = planet_prev_entity[current_entity_id]; current_entity_type = prev_entity_type; current_entity_id = prev_entity_id; } else if (current_entity_type == 2) { // station auto [prev_entity_type, prev_entity_id] = station_prev_entity[current_entity_id]; current_entity_type = prev_entity_type; current_entity_id = prev_entity_id; } } reverse(route.begin(), route.end()); return route; } void update_route_info() { route_info.emplace_back(1, 0); for (int i = 0; i < planet_num; i++) { auto path = find_shortest_route(planet_visit_order[i], planet_visit_order[i + 1]); for (auto &entity: path) route_info.push_back(entity); } } void solve() { update_route_info(); } void output_ans() { for (auto &station: station_pos) { cout << station.first << " " << station.second << endl; } cout << route_info.size() << endl; for (auto &route: route_info) { cout << route.first << " " << route.second + 1 << endl; } } int main(int argc, char *argv[]) { cin.tie(0); ios::sync_with_stdio(false); receive_input(); init(); solve(); output_ans(); return 0; }