#include #include #include #include #include #include #include #define mkt make_tuple #define rep(i, n) for (int i = 0; i < (int)(n); ++i) #define all(v) v.begin(), v.end() using namespace std; using ll = long long; template void chmin(T &a, const T &b) { if (a > b) a = b; } template void chmax(T &a, const T &b) { if (a < b) a = b; } constexpr int N = 100; constexpr int M = 8; constexpr int ALPHA = 5; constexpr int PLANET = 1; constexpr int STATION = 2; class Timer { public: chrono::time_point start; Timer() {} void init() { start = chrono::system_clock::now(); } int get_ms() { auto cur = chrono::system_clock::now(); return chrono::duration_cast(cur - start).count(); } }; struct Coordinate { int x; int y; Coordinate(int x = -1, int y = -1) : x(x), y(y) {} bool operator==(const Coordinate &rhs) const { return x == rhs.x && y == rhs.y; } bool operator!=(const Coordinate &rhs) const { return x != rhs.x || y != rhs.y; } int get_manhattan_dist(const Coordinate &other) const { int dx = abs(x - other.x); int dy = abs(y - other.y); return dx + dy; } int get_euclid_dist_squared(const Coordinate &other) const { int dx = abs(x - other.x); int dy = abs(y - other.y); return dx * dx + dy * dy; } }; class DisjointSet { public: int N; vector par, rank; vector sz; DisjointSet() {} DisjointSet(int N) : N(N), par(N), rank(N), sz(N) { for (int i = 0; i < N; i++) make_set(i); } bool same(int x, int y) { return leader(x) == leader(y); } void unite(int x, int y) { if (same(x, y)) return; link(leader(x), leader(y)); } int leader(int x) { if (x != par[x]) par[x] = leader(par[x]); return par[x]; } int size(int x) { return sz[leader(x)]; } private: void make_set(int x) { par[x] = x; rank[x] = 0; sz[x] = 1; } void link(int x, int y) { if (rank[x] > rank[y]) swap(x, y); par[x] = y; sz[y] += sz[x]; if (rank[x] == rank[y]) { ++rank[y]; } } }; struct Planet { int id; Coordinate pos; Planet(int id, Coordinate pos) : id(id), pos(pos) {} }; struct Station { int id; Coordinate pos; Station(int id, Coordinate pos) : id(id), pos(pos) {} }; struct Input { vector planets; Input(vector planets) : planets(planets) {} }; struct Output { int type; int id; Output(int type, int id) : type(type), id(id) {} }; Timer timer; Input read_input() { // Timer timer; timer.init(); int n, m; cin >> n >> m; vector planets; for (int i = 0; i < N; i++) { int a, b; cin >> a >> b; planets.emplace_back(i, Coordinate(a, b)); } Input input(planets); return input; } void output(vector stations, vector outputs) { for (auto stat : stations) cout << stat.pos.x << " " << stat.pos.y << "\n"; cout << outputs.size() << "\n"; for (auto out : outputs) cout << out.type << " " << out.id + 1 << "\n"; } pair>, vector>> init_dist(const vector &planets, const vector &stations) { vector objects; rep(i, N) objects.emplace_back(planets[i].pos); rep(i, M) objects.emplace_back(stations[i].pos); const int V = objects.size(); const int inf = 1e9; vector> dist(V, vector(V, inf)); vector> nxt(V, vector(V, inf)); rep(i, V) rep(j, V) { int coef = 1; if (i < N) coef *= 5; if (j < N) coef *= 5; int cost = coef * objects[i].get_euclid_dist_squared(objects[j]); dist[i][j] = cost; nxt[i][j] = j; } rep(k, V) rep(i, V) rep(j, V) { if (dist[i][j] > dist[i][k] + dist[k][j]) { dist[i][j] = dist[i][k] + dist[k][j]; nxt[i][j] = nxt[i][k]; } } return make_pair(dist, nxt); } vector solve_TSP_by_2_opt(const vector &planets, const vector &stations) { const auto [dist, nxt] = init_dist(planets, stations); vector visit_order; rep(i, N) visit_order.push_back(i); visit_order.push_back(0); const int V = visit_order.size(); const int TIME_LIMIT = 950; random_device seed_gen; mt19937 rng(seed_gen()); while (1) { if (timer.get_ms() > TIME_LIMIT) break; int a = 1 + rng() % (V - 2); int b = 1 + rng() % (V - 2); while (abs(a - b) <= 1) b = 1 + rng() % (V - 2); if (a > b) swap(a, b); int bef_dist = dist[visit_order[a]][visit_order[a + 1]] + dist[visit_order[b]][visit_order[b + 1]]; int aft_dist = dist[visit_order[a]][visit_order[b]] + dist[visit_order[a + 1]][visit_order[b + 1]]; if (bef_dist > aft_dist) { reverse(visit_order.begin() + a + 1, visit_order.begin() + b + 1); } } vector outputs; outputs.emplace_back(PLANET, 0); rep(i, V - 1) { int a = visit_order[i]; int b = visit_order[i + 1]; int now = a; while (nxt[now][b] != b) { if (nxt[now][b] < N) outputs.emplace_back(PLANET, nxt[now][b]); else outputs.emplace_back(STATION, nxt[now][b] - N); now = nxt[now][b]; } if (b < N) outputs.emplace_back(PLANET, b); else outputs.emplace_back(STATION, b - N); } return outputs; } void solve(const Input &input) { vector stations; rep(i, M) stations.emplace_back(i, input.planets[i].pos); vector outputs = solve_TSP_by_2_opt(input.planets, stations); output(stations, outputs); cerr << "end time: " << timer.get_ms() << "[ms]" << endl; } int main() { cin.tie(nullptr); ios::sync_with_stdio(false); Input input = read_input(); solve(input); return 0; }