#include using namespace std; #define rep(i, n) for (int i = 0; i < (int)(n); i++) #define ALL(v) (v).begin(), (v).end() using ll = long long; constexpr int MOD = 1000000007; constexpr int N = 100; constexpr int M = 8; constexpr ll A = 5; int a[N], b[N]; ll dist[N + M][N + M]; constexpr double TIMELIMIT = 0.98; struct XorShift { unsigned int x, y, z, w, t; XorShift(int seed) { mt19937 rnd(seed); x = rnd(); y = rnd(); z = rnd(); w = rnd(); t = 1; } int rand() { t = x ^ (x << 11); x = y; y = z; z = w; w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)); return w & 0x7fffffff; } } rnd(rand()); struct Timer { chrono::system_clock::time_point start, now; Timer() { start = chrono::system_clock::now(); } double getTime() { now = chrono::system_clock::now(); return chrono::duration(now - start).count(); } }; struct State { int c[M], d[M]; int order_of_planets[N + 1]; ll score; }; ll dfs_calc(int from, int to) { int mn = dist[from][to]; int mid = -1; for (int v = 0; v < N + M; v++) { if (dist[from][v] + dist[v][to] < mn) { mn = dist[from][v] + dist[v][to]; mid = v; } } if (mid == -1) return dist[from][to]; return dfs_calc(from, mid) + dfs_calc(mid, to); } vector dfs_output(int from, int to) { int mn = dist[from][to]; int mid = -1; for (int v = 0; v < N + M; v++) { if (dist[from][v] + dist[v][to] < mn) { mn = dist[from][v] + dist[v][to]; mid = v; } } if (mid == -1) return vector(); auto l = dfs_output(from, mid); auto r = dfs_output(mid, to); l.emplace_back(mid); for (int v : r) { l.emplace_back(v); } return l; } void calc(State& state) { for (int i = 0; i < M; i++) { for (int j = 0; j < M; j++) { dist[i][j] = dist[j][i] = (state.c[i] - state.c[j]) * (state.c[i] - state.c[j]) + (state.d[i] - state.d[j]) * (state.d[i] - state.d[j]); } for (int j = 0; j < N; j++) { dist[i][j + M] = dist[j + M][i] = A * ((state.c[i] - a[j]) * (state.c[i] - a[j]) + (state.d[i] - b[j]) * (state.d[i] - b[j])); } } state.score = 0; rep(i, N) { state.score += dfs_calc(state.order_of_planets[i] + M, state.order_of_planets[i + 1] + M); } } void output(State& state) { for (int i = 0; i < M; i++) { for (int j = 0; j < M; j++) { dist[i][j] = dist[j][i] = (state.c[i] - state.c[j]) * (state.c[i] - state.c[j]) + (state.d[i] - state.d[j]) * (state.d[i] - state.d[j]); } for (int j = 0; j < N; j++) { dist[i][j + M] = dist[j + M][i] = A * ((state.c[i] - a[j]) * (state.c[i] - a[j]) + (state.d[i] - b[j]) * (state.d[i] - b[j])); } } vector> ans; rep(i, N) { ans.emplace_back(1, state.order_of_planets[i] + 1); auto vec = dfs_output(state.order_of_planets[i] + M, state.order_of_planets[i + 1] + M); for (int v : vec) { ans.emplace_back(1 + (v < M), v - M * (M <= v) + 1); } } ans.emplace_back(1, state.order_of_planets[N] + 1); rep(i, M) { cout << state.c[i] << " " << state.d[i] << endl; } cout << ans.size() << endl; for (auto p : ans) { cout << p.first << " " << p.second << endl; } } void init(State& state) { int idx = 0; for (int x = 200; x <= 800; x += 300) { for (int y = 200; y <= 800; y += 300) { if (x == 800 && y == 800) break; state.c[idx] = x, state.d[idx++] = y; } } bool visited[N] = {}; int cur = 0; visited[cur] = true; state.order_of_planets[0] = 0; for (int i = 1; i < N; i++) { int mn = INT_MAX; int nxt = 0; rep(to, N) { if (visited[to]) continue; if (dist[cur + M][to + M] < mn) { mn = dist[cur + M][to + M]; nxt = to; } } cur = nxt; visited[cur] = true; state.order_of_planets[i] = cur; } state.order_of_planets[N] = 0; calc(state); } void modify(State& state) { if (rnd.rand() % 2) { int idx = rnd.rand() % M; state.c[idx] = rnd.rand() % 1001; state.d[idx] = rnd.rand() % 1001; } else { swap(state.order_of_planets[rnd.rand() % (N - 1) + 1], state.order_of_planets[rnd.rand() % (N - 1) + 1]); } calc(state); } void solve(State& state) { int steps = 0; Timer tmr; double nowclock = 0, startclock = tmr.getTime(); while (true) { if (steps % 100 == 0) { nowclock = tmr.getTime(); if (nowclock - startclock > TIMELIMIT) break; } State newstate = state; modify(newstate); if (newstate.score < state.score) { state = newstate; } steps++; } cerr << "score : " << state.score << endl; cerr << "steps : " << steps << endl; } void input() { int _N, _M; cin >> _N >> _M; rep(i, N) { cin >> a[i] >> b[i]; } rep(i, N) { rep(j, N) { dist[i + M][j + M] = A * A * ((a[i] - a[j]) * (a[i] - a[j]) + (b[i] - b[j]) * (b[i] - b[j])); } } } signed main() { input(); State state; init(state); solve(state); output(state); return 0; }