#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define endl '\n' #define ALL(v) (v).begin(), (v).end() #define RALL(v) (v).rbegin(), (v).rend() #define UNIQ(v) (v).erase(unique((v).begin(), (v).end()), (v).end()) typedef long long ll; typedef long double ld; typedef pair P; typedef complex comp; typedef vector< vector > matrix; struct pairhash { public: template size_t operator()(const pair &x) const { size_t seed = hash()(x.first); return hash()(x.second) + 0x9e3779b9 + (seed<<6) + (seed>>2); } }; const int INF = 1e9 + 9; //const ll INF = 1e18 + 9; const ll MOD = 1e9 + 7; //const ll MOD = 998244353; const double EPS = 1e-8; const double PI = acos(-1); int n, m; int a[110], b[110]; int dist[110][110]; const int alpha = 5; const int alpha2 = 25; double get_elapsed_time(struct timeval *begin, struct timeval *end) { return (end->tv_sec - begin->tv_sec) * 1000 + (end->tv_usec - begin->tv_usec) / 1000.0; } unsigned long xor128(void) { static unsigned long x=123456789,y=362436069,z=521288629,w=88675123; unsigned long t; t=(x^(x<<11));x=y;y=z;z=w; return( w=(w^(w>>19))^(t^(t>>8)) ); } // [0, k) int rand(int k) { return xor128() % k; } // [a, b) int rand(int a, int b) { return a + xor128() % (b - a); } // [0, 1) double rand_double() { return (double)rand(INF) / INF; } int calc_dist(const int i, const int j) { return (a[i] - a[j]) * (a[i] - a[j]) + (b[i] - b[j]) * (b[i] - b[j]); } int calc_dist(const int i, const pair& p) { return (a[i] - p.first) * (a[i] - p.first) + (b[i] - p.second) * (b[i] - p.second); } int calc_dist(const pair& p0, const pair& p1) { return (p0.first - p1.first) * (p0.first - p1.first) + (p0.second - p1.second) * (p0.second - p1.second); } int calc_diff(const int i, const int j, const vector& order) { const int i0 = order[i], i1 = order[i-1]; const int j0 = order[j], j1 = order[j+1]; const int d_cur = dist[i1][i0] + dist[j0][j1]; const int d_next = dist[i1][j0] + dist[i0][j1]; return d_cur - d_next; } int calc_diff_s(const int i, const int j, const vector& order, const vector& order_rev, const vector& exist) { const int order_i = order_rev[i], order_j = order_rev[j]; const int i_prev = order[max(0, order_i-1)]; const int i_next = order[order_i+1]; const int j_prev = order[max(0, order_j-1)]; const int j_next = order[order_j+1]; int d_cur = 0; d_cur += (exist[i_prev] >= 0 ? dist[i_prev][i] : alpha * dist[i_prev][i]); d_cur += (exist[i_next] >= 0 ? dist[i][i_next] : alpha * dist[i][i_next]); d_cur += (exist[j_prev] >= 0 ? alpha * dist[j_prev][j] : alpha2 * dist[j_prev][j]); d_cur += (exist[j_next] >= 0 ? alpha * dist[j][j_next] : alpha2 * dist[j][j_next]); int d_next = 0; d_next += (exist[i_prev] >= 0 ? alpha * dist[i_prev][i] : alpha2 * dist[i_prev][i]); d_next += (exist[i_next] >= 0 ? alpha * dist[i][i_next] : alpha2 * dist[i][i_next]); d_next += (exist[j_prev] >= 0 ? dist[j_prev][j] : alpha * dist[j_prev][j]); d_next += (exist[j_next] >= 0 ? dist[j][j_next] : alpha * dist[j][j_next]); return d_cur - d_next; } int calc_tour_dist(const vector& order, const vector>& stations) { int d = 0; for (int i = 0; i < n; i++) { int d0 = alpha2 * dist[order[i]][order[i+1]]; for (const auto& p : stations) { d0 = min(d0, alpha * (calc_dist(order[i], p) + calc_dist(order[i+1], p))); } for (int j = 0; j < m; j++) { for (int k = 0; k < m; k++) { if (j == k) continue; d0 = min(d0, alpha * calc_dist(order[i], stations[j]) + calc_dist(stations[j], stations[k]) + alpha * calc_dist(order[i+1], stations[k])); } } d += d0; } return d; } int calc_tour_dist(const vector& order, const pair& p) { int d = 0; for (int i = 0; i < n; i++) { int d0 = alpha2 * dist[order[i]][order[i+1]]; d0 = min(d0, alpha * (calc_dist(order[i], p) + calc_dist(order[i+1], p))); d += d0; } return d; } vector> make_tour(const vector& order, const vector>& stations) { vector> res; res.push_back(make_pair(1, 1)); for (int i = 0; i < n; i++) { int s0 = -1, s1 = -1; int d0 = alpha2 * dist[order[i]][order[i+1]]; for (int j = 0; j < m; j++) { const auto& p = stations[j]; const int d1 = alpha * (calc_dist(order[i], p) + calc_dist(order[i+1], p)); if (d0 > d1) { d0 = d1; s0 = j; } } for (int j = 0; j < m; j++) { for (int k = 0; k < m; k++) { if (j == k) continue; const int d1 = alpha * calc_dist(order[i], stations[j]) + calc_dist(stations[j], stations[k]) + alpha * calc_dist(order[i+1], stations[k]); if (d0 > d1) { d0 = d1; s0 = j; s1 = k; } } } if (s0 < 0) { res.push_back(make_pair(1, order[i+1]+1)); } else if (s1 < 0) { res.push_back(make_pair(2, s0+1)); res.push_back(make_pair(1, order[i+1]+1)); } else { res.push_back(make_pair(2, s0+1)); res.push_back(make_pair(2, s1+1)); res.push_back(make_pair(1, order[i+1]+1)); } } return res; } void init() { for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) dist[i][j] = calc_dist(i, j); } pair>, vector>> solve() { init(); vector order; for (int i = 0; i < n; i++) order.push_back(i); order.push_back(0); struct timeval t1, t2; gettimeofday(&t1, NULL); int iter; double T_init = 10; double T_end = 0.01; double T = T_init; double TIME_LIMIT = 100; int move = 0; for (iter = 1; ; iter++) { int i, j; i = rand(1, n); while (i == (j = rand(1, n))); if (i > j) swap(i, j); const int diff = calc_diff(i, j, order); if (diff > 0 || exp(diff/T) > rand_double()) { reverse(order.begin()+i, order.begin()+j+1); } if (iter % 100 == 0) { gettimeofday(&t2, NULL); const double et = get_elapsed_time(&t1, &t2); if (et > TIME_LIMIT) break; T = (T_end - T_init) / TIME_LIMIT * et + T_init; } } vector order_rev(n); int d_plain = 0; for (int i = 0; i < n; i++) { order_rev[order[i]] = i; d_plain += alpha2 * dist[order[i]][order[i+1]]; } vector>> vec; for (int x = 10; x < 1000; x+=10) { for (int y = 10; y < 1000; y+=10) { const int d = calc_tour_dist(order, make_pair(x, y)); vec.push_back(make_pair(d, make_pair(x, y))); } } sort(ALL(vec)); vector> cand; const int K = 100; for (const auto& p : vec) { const auto& pos = p.second; bool near = false; for (const auto& q : cand) { const int d = calc_dist(pos, q); if (d < 5000) { near = true; break; } } if (near) continue; cand.push_back(pos); if ((int)cand.size() >= K) break; } int p[n]; for (int i = 0; i < K; i++) p[i] = i; vector> stations; vector s_pos; vector exist(K, -1); for (int i = 0; i < m; i++) { const int j = rand(n-i); const int idx = p[j]; stations.push_back(cand[idx]); s_pos.push_back(idx); exist[p[j]] = i; swap(p[j], p[n-i-1]); } gettimeofday(&t1, NULL); T_init = 100000; T_end = 0.01; T = T_init; TIME_LIMIT = 500; move = 0; for (iter = 1; ; iter++) { const int s_idx = rand(m); const int i = s_pos[s_idx]; int j; while (true) { j = rand(K); if (exist[j] < 0) break; } const int d_cur = calc_tour_dist(order, stations); //stations[s_idx].first = a[j]; //stations[s_idx].second = b[j]; stations[s_idx] = cand[j]; const int d_next = calc_tour_dist(order, stations); const int diff = d_cur - d_next; if (diff > 0 || exp(diff/T) > rand_double()) { s_pos[s_idx] = j; exist[i] = -1; exist[j] = s_idx; move++; } else { stations[s_idx] = cand[i]; //stations[s_idx].first = a[i]; //stations[s_idx].second = b[i]; } if (iter % 100 == 0) { gettimeofday(&t2, NULL); const double et = get_elapsed_time(&t1, &t2); if (et > TIME_LIMIT) break; T = (T_end - T_init) / TIME_LIMIT * et + T_init; } } cerr << "iter: " << iter << endl; cerr << "move: " << move << endl; gettimeofday(&t1, NULL); T_init = 200; T_end = 0.01; T = T_init; TIME_LIMIT = 380; move = 0; for (iter = 1; ; iter++) { const int s_idx = rand(m); const int dx = rand(1, 20) * (rand(2) == 0 ? -1 : 1); const int dy = rand(1, 20) * (rand(2) == 0 ? -1 : 1); const int d_cur = calc_tour_dist(order, stations); stations[s_idx].first += dx; stations[s_idx].second += dy; const int d_next = calc_tour_dist(order, stations); const int diff = d_cur - d_next; if (diff > 0 || exp(diff/T) > rand_double()) { move++; } else { stations[s_idx].first -= dx; stations[s_idx].second -= dy; } if (iter % 100 == 0) { gettimeofday(&t2, NULL); const double et = get_elapsed_time(&t1, &t2); if (et > TIME_LIMIT) break; T = (T_end - T_init) / TIME_LIMIT * et + T_init; } } cerr << "iter: " << iter << endl; cerr << "move: " << move << endl; vector> res = make_tour(order, stations); return make_pair(stations, res); } void input() { cin >> n >> m; for (int i = 0; i < n; i++) cin >> a[i] >> b[i]; } void output(const pair>, vector>>& res) { for (const auto& s : res.first) { cout << s.first << " " << s.second << endl; } cout << (int)res.second.size() << endl; for (const auto& s : res.second) { cout << s.first << " " << s.second << endl; } } int main() { ios::sync_with_stdio(false); cin.tie(0); cout << fixed << setprecision(15); input(); const auto& res = solve(); output(res); }