#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 x_sum(k), y_sum(k), cnt(k); vector perm(points.size()); iota(perm.begin(), perm.end(), 0); shuffle(perm.begin(), perm.end(), mt); for(int i = 0; i < points.size(); i++){ x_sum[i%k] += points[i].first; y_sum[i%k] += points[i].second; cnt[i%k]++; } vector cur_ans; for(int i = 0; i < k; i++) cur_ans.push_back(P(x_sum[i]/cnt[i], y_sum[i]/cnt[i])); 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; } bool seen_shortest_path[n+m]; 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); seen_shortest_path[cur] = true; for(int i = 0; i < sz; i++){ if(i == cur) continue; if(seen_shortest_path[i]) continue; if(dist[s][cur] == dist[s][i]+g[i][cur]){ cur = i; break; } assert(i != sz-1); } } for(int v: ans) seen_shortest_path[v] = false; ans.push_back(s); reverse(ans.begin(), ans.end()); return ans; } vector greedy_tour(const vector> &dist, int s){ vector visited(n); int cur = s; 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; } return ans; } ll eval_stations(vector

stations){ 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; }; 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 tour = greedy_tour(dist, 0); ll len = 0; for(int i = 0; i < n; i++){ int j = (i+1)%n; len += dist[tour[i]][tour[j]]; } return len; } vector

improve_stations(vector

initial_solution, double time_limit, double start_temp = 50.0, double end_temp = 0.0){ clock_t start = clock(); auto ans = initial_solution; ll cur_score = eval_stations(ans); double remaining_time = time_limit - (double)(clock()-start)/CLOCKS_PER_SEC; double temperature = start_temp; for(int iter = 0;; iter++){ clock_t cur_time = clock(); remaining_time = time_limit - (double)(cur_time-start)/CLOCKS_PER_SEC; temperature = end_temp + (start_temp-end_temp) * (remaining_time/time_limit); if(remaining_time < 0.0) { // debug_value(iter) break; } int idx = mt()%m; int dx = (mt()%21)-10, dy = (mt()%21)-10; auto new_stations = ans; new_stations[idx].first += dx; chmax(new_stations[idx].first, 0); chmin(new_stations[idx].first, 1000); new_stations[idx].second += dy; chmax(new_stations[idx].second, 0); chmin(new_stations[idx].second, 1000); if(chmin(cur_score, eval_stations(new_stations))){ ans = new_stations; } } return ans; } class TspSolution{ public: int sz; ll len; vector tour; vector> dist; ll tour_len(){ ll len = 0; for(int i = 0; i < sz; i++){ int j = (i+1)%sz; len += dist[tour[i]][tour[j]]; } return len; } TspSolution(vector tour, vector> dist): sz(tour.size()), tour(tour), dist(dist){ len = tour_len(); } pair suggest_two_opt(){ int i = (mt()%(sz-1)) + 1; int j = (mt()%(sz-1)) + 1; while(i == j) j = (mt()%(m-1)) + 1; if(i > j) swap(i, j); return make_pair(i, j); } ll swapped_diff(int i, int j){ int increase = dist[tour[i]][tour[j]] + dist[tour[(i+1)%sz]][tour[(j+1)%sz]]; int decrease = dist[tour[i]][tour[(i+1)%sz]] + dist[tour[j]][tour[(j+1)%sz]]; return increase-decrease; }; void apply_swap(int i, int j){ vector new_tour; for(int k = 0; k <= i; k++) new_tour.push_back(tour[k]); for(int k = j; k >= i+1; k--) new_tour.push_back(tour[k]); for(int k = j+1; k < sz; k++) new_tour.push_back(tour[k]); tour = new_tour; len = tour_len(); }; }; vector solve_tsp(const vector> &dist, int s, double time_limit, double start_temp = 50000.0, double end_temp = 0.0){ clock_t start = clock(); auto sol = TspSolution(greedy_tour(dist, s), dist); // sa settings uniform_real_distribution rand_dist(0.0, 1.0); auto accept_proba = [&](int diff, double temp){ return min(1.0, exp((double)-diff/temp)); }; auto try_two_opt = [&](double temperature){ auto [i, j] = sol.suggest_two_opt(); int diff = sol.swapped_diff(i, j); if(rand_dist(mt) <= accept_proba(diff, temperature)) sol.apply_swap(i, j); // if(diff < 0) sol.apply_swap(i, j); }; double remaining_time = time_limit - (double)(clock()-start)/CLOCKS_PER_SEC; double temperature = start_temp; for(int iter = 0;; iter++){ if(iter%100 == 0){ clock_t cur_time = clock(); remaining_time = time_limit - (double)(cur_time-start)/CLOCKS_PER_SEC; temperature = end_temp + (start_temp-end_temp) * (remaining_time/time_limit); } if(remaining_time < 0.0) { break; } try_two_opt(temperature); } auto ans = sol.tour; ans.push_back(s); 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); stations = improve_stations(stations, 0.5); 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, 0, 0.4); 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; }