#include #include #include #include #include #include #include #include #include #include #include #include #include #include std::random_device rnd; std::mt19937 mt(rnd()); int randint(const int l, const int r){ return mt()%(r - l) + l; } #define debug_value(x) cerr << "line" << __LINE__ << ":<" << __func__ << ">:" << #x << "=" << x << endl; #define debug(x) cerr << "line" << __LINE__ << ":<" << __func__ << ">:" << x << endl; template inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; } template inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; } using namespace std; typedef long long ll; template vector> vec2d(int n, int m, T v){ return vector>(n, vector(m, v)); } template vector>> vec3d(int n, int m, int k, T v){ return vector>>(n, vector>(m, vector(k, v))); } template void print_vector(vector v, char delimiter=' '){ if(v.empty()) { cout << endl; return; } for(int i = 0; i+1 < v.size(); i++) cout << v[i] << delimiter; cout << v.back() << endl; } const ll infll = 1e+18; vector> warshallfloyd(vector> g){ int n = g.size(); vector> dist(n, vector(n)); for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ dist[i][j] = g[i][j]; } dist[i][i] = 0; } for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ for(int k = 0; k < n; k++){ ll new_len = dist[j][i] + dist[i][k]; dist[j][k] = min(new_len, dist[j][k]); } } } return dist; } const int n = 100; const int m = 8; int a[n], b[n]; using P = pair; using Pdd = pair; void get_input(){ int dummy; cin >> dummy >> dummy; for(int i = 0; i < n; i++) cin >> a[i] >> b[i]; } double dist(double x0, double y0, double x1, double y1){ double dx = x0-x1; double dy = y0-y1; return sqrt(dx*dx+dy*dy); } vector

k_means(vector

points, int k=m, int iter=100){ vector cur_ans; for(int i = 0; i < k; i++) cur_ans.push_back(Pdd(randint(0, 1000), randint(0, 1000))); for(int i = 0; i < iter; i++){ vector> clusters(k); for(auto [x, y]: points){ int idx = -1; double min_dist = 1e9; for(int j = 0; j < k; j++){ auto [xx, yy] = cur_ans[j]; if(chmin(min_dist, dist(xx, yy, x, y))) idx = j; } clusters[idx].push_back(P(x, y)); } for(int i = 0; i < k; i++){ int sz = clusters[i].size(); if(sz == 0) continue; int x_sum = 0, y_sum = 0; for(auto [x, y]: clusters[i]){ x_sum += x; y_sum += y; } cur_ans[i] = P(double(x_sum)/double(sz), double(y_sum)/double(sz)); } } vector

ans; for(int i = 0; i < k; i++){ auto [xx, yy] = cur_ans[i]; int x = max(0, (int)round(xx)); int y = max(0, (int)round(yy)); ans.push_back(P(x, y)); } return ans; } vector shortest_path(const vector> &dist, const vector> &g, const int s, const int t){ int sz = dist.size(); int cur = t; vector ans; while(cur != s){ ans.push_back(cur); for(int i = 0; i < sz; i++){ if(i == cur) continue; if(dist[s][cur] == dist[s][i]+g[i][cur]){ cur = i; break; } assert(i != sz-1); } } ans.push_back(s); reverse(ans.begin(), ans.end()); return ans; } vector solve_tsp(const vector> &dist){ vector visited(n); int cur = 0; vector ans; for(int i = 0; i < n; i++){ ans.push_back(cur); visited[cur] = true; ll min_dist = infll; int nx = -1; for(int j = 0; j < n; j++){ if(visited[j]) continue; if(chmin(min_dist, dist[cur][j])){ nx = j; } } cur = nx; } ans.push_back(0); return ans; } class Solution{ public: vector

stations; vector tp; vector idx; Solution(vector

stations, vector tp, vector idx): stations(stations), tp(tp), idx(idx) {} void output(){ for(auto [x, y]: stations) cout << x << ' ' << y << endl; int v = tp.size(); assert(idx.size() == v); cout << v << endl; for(int i = 0; i < v; i++) { cout << tp[i] << ' ' << idx[i]+1 << endl; } } ll eval(){ int v = tp.size(); auto get_x = [&](int tp, int idx){ if(tp == 1) return a[idx]; return stations[idx].first; }; auto get_y = [&](int tp, int idx){ if(tp == 1) return b[idx]; return stations[idx].second; }; ll s = 0; for(int i = 0; i < v-1; i++) { ll dx = get_x(tp[i], idx[i])-get_x(tp[i+1], idx[i+1]); ll dy = get_y(tp[i], idx[i])-get_y(tp[i+1], idx[i+1]); ll coef = (tp[i] == 1 ? 5 : 1)*(tp[i+1] == 1 ? 5 : 1); s += (dx*dx+dy*dy)*coef; } ll ans = round((double)1000000000/(1000+sqrt(s))); return ans; } }; Solution solve(){ auto g = vec2d(n+m, n+m, infll); auto coef = [](int i, int j){ if(i < n && j < n) return 25; if(i < n || j < n) return 5; return 1; }; vector

planets(n); for(int i = 0; i < n; i++) planets[i] = P(a[i], b[i]); auto stations = k_means(planets); auto get_x = [&](int i){ if(i < n) return a[i]; return stations[i-n].first; }; auto get_y = [&](int i){ if(i < n) return b[i]; return stations[i-n].second; }; for(int i = 0; i < n+m; i++){ for(int j = i+1; j < n+m; j++){ ll dx = get_x(i)-get_x(j), dy = get_y(i)-get_y(j); ll dist = (dx*dx+dy*dy)*coef(i, j); g[i][j] = dist; g[j][i] = dist; } } auto dist = warshallfloyd(g); auto ord = solve_tsp(dist); assert(ord.size() == n+1); auto sol = Solution(stations, vector(), vector()); for(int i = 0; i < n; i++){ int s = ord[i], t = ord[i+1]; auto path = shortest_path(dist, g, s, t); auto add = [&](int idx){ if(idx < n) { sol.tp.push_back(1); sol.idx.push_back(idx); }else{ sol.tp.push_back(2); sol.idx.push_back(idx-n); } }; if(i == 0){ add(path[0]); } for(int j = 1; j < path.size(); j++){ add(path[j]); } } return sol; } int main(){ ios::sync_with_stdio(false); cin.tie(0); cout << setprecision(10) << fixed; get_input(); auto sol = solve(); sol.output(); // cerr << sol.eval() << endl; }