#include // #include "atcoder/all" using namespace std; using i64 = long long; const i64 MOD = 1e9 + 7; const i64 INF = i64(1e18); template bool chmin(T& x, T y){ if(x > y){ x = y; return true; } return false; } template bool chmax(T& x, T y){ if(x < y){ x = y; return true; } return false; } uint32_t rnd(){ static uint32_t x = 123456789, y = 362436069, z = 521288629, w = 0; uint32_t t = x ^ (x << 11); x = y; y = z; z = w; w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)); return w; } double rnd_double(){ return 1.0 * rnd() / numeric_limits::max(); } // #define OPTIMIZE namespace params{ void load_params(){ ifstream ifs("../params.txt"); assert(ifs.is_open()); } } // doc: https://shibh308.github.io/library/library/lib/functions/tsp.cpp.html template vector tsp(int n, vector init, vector> dist, int iter_num){ // 始点=終点のTSP n <= 2 とかでバグりそうなので注意 vector v = init; vector inv(n); T now_dist = 0; for(int i = 0; i < n; ++i){ inv[v[i]] = i; now_dist += dist[v[i]][v[(i + 1) % n]]; } // 前計算 vector>> near_vertexes(n); for(int i = 0; i < n; ++i){ for(int j = 0; j < n; ++j){ near_vertexes[i].emplace_back(dist[i][j], j); } sort(near_vertexes[i].begin(), near_vertexes[i].end()); } auto dist_check = [&](){ auto di = dist[0][0]; for(int i = 0; i < n; ++i){ di += dist[v[i]][v[(i + 1) % n]]; } assert(abs(now_dist - di) <= 1e-6); }; auto update = [&](int i1, int i3){ int i2 = (i1 + 1) % n; int i4 = (i3 + 1) % n; if(i1 == i3 || i2 == i3 || i1 == i4 || i2 == i4) return false; if(dist[v[i1]][v[i2]] + dist[v[i3]][v[i4]] <= dist[v[i1]][v[i3]] + dist[v[i2]][v[i4]]) return false; auto improve = (dist[v[i1]][v[i2]] + dist[v[i3]][v[i4]]) - (dist[v[i1]][v[i3]] + dist[v[i2]][v[i4]]); now_dist -= improve; int d1 = (i2 < i3 ? i3 - i2 : i3 + n - i2); int d2 = (i4 < i1 ? i1 - i4 : i1 + n - i4); if(d1 >= d2){ swap(i1, i3); swap(i2, i4); } int st = i2; int en = i2 < i3 ? i3 : i3 + n; while(st < en){ inv[v[en % n]] = st % n; inv[v[st % n]] = en % n; swap(v[st % n], v[en % n]); ++st, --en; } // バグが怖い時用 // dist_check(); return true; }; auto neighbors_search = [&](){ for(int i = 0; i < n; ++i){ int idx1 = i; int idx2 = (i + 1) % n; int v1 = v[idx1]; int v2 = v[idx2]; for(auto [d, v3] : near_vertexes[v1]){ if(v3 == v2) break; int idx3 = inv[v3]; if(update(idx1, idx3)){ return true; } } for(auto [d, v4] : near_vertexes[v2]){ if(v4 == v1) break; int idx3 = (inv[v4] + n - 1) % n; if(update(idx1, idx3)){ return true; } } } return false; }; auto double_bridge = [&](){ vector r{rnd() % n, rnd() % n, rnd() % n, rnd() % n}; sort(r.begin(), r.end()); if(r[0] == r[1] || r[1] == r[2] || r[2] == r[3]){ return true; } // (r[3] + 1, r[0]) => (r[2] + 1, r[3]) => (r[1] + 1, r[2]) => (r[0] + 1, r[1]) auto diff = dist[0][0]; diff -= dist[v[r[0]]][v[r[0] + 1]]; diff -= dist[v[r[1]]][v[r[1] + 1]]; diff -= dist[v[r[2]]][v[r[2] + 1]]; diff -= dist[v[r[3]]][v[(r[3] + 1) % n]]; diff += dist[v[r[0]]][v[r[2] + 1]]; diff += dist[v[r[3]]][v[r[1] + 1]]; diff += dist[v[r[2]]][v[r[0] + 1]]; diff += dist[v[r[1]]][v[(r[3] + 1) % n]]; now_dist += diff; vector nex; nex.reserve(n); for(int i = r[3] + 1; i < n; ++i) nex.emplace_back(v[i]); for(int i = 0; i <= r[0]; ++i) nex.emplace_back(v[i]); for(int i = r[2] + 1; i <= r[3]; ++i) nex.emplace_back(v[i]); for(int i = r[1] + 1; i <= r[2]; ++i) nex.emplace_back(v[i]); for(int i = r[0] + 1; i <= r[1]; ++i) nex.emplace_back(v[i]); v = move(nex); return false; }; auto best = make_pair(now_dist, v); for(int i = 0; i < iter_num; ++i){ if(i){ while(double_bridge()); } while(neighbors_search()); if(!chmin(best, make_pair(now_dist, v))){ tie(now_dist, v) = best; } } for(int i = 0; i < n; ++i){ if(v[i] == 0){ vector res; for(int j = 0; j < n; ++j){ res.emplace_back(v[(i + j) % n]); } return res; } } // return now_dist; return v; } constexpr int n = 100; constexpr int m = 8; constexpr int alpha = 5; array ax, ay; void read_file(istream& ifs){ int a; ifs >> a >> a; // TODO: input for(int i = 0; i < n; ++i){ ifs >> ax[i] >> ay[i]; } } clock_t st; void solve(){ vector> a_dist(n, vector(n)); vector bx(n), by(n); auto raw_dis = [&](auto p1, auto q1, auto p2, auto q2){ i64 dx = (p1 == 0 ? ax[q1] : bx[q1]) - (p2 == 0 ? ax[q2] : bx[q2]); i64 dy = (p1 == 0 ? ay[q1] : by[q1]) - (p2 == 0 ? ay[q2] : by[q2]); return dx * dx + dy * dy; }; auto dis = [&](auto p1, auto q1, auto p2, auto q2){ int alp = 1; alp *= (p1 == 0 ? 5 : 1); alp *= (p2 == 0 ? 5 : 1); return raw_dis(p1, q1, p2, q2) * alp; }; for(int i = 0; i < n; ++i){ for(int j = 0; j < n; ++j){ a_dist[i][j] = dis(0, i, 0, j); } } vector> idxes_x(1001); for(int i = 0; i < n; ++i){ idxes_x[ax[i]].emplace_back(i); } /* vector> points(1001, vector(1001, 0)); for(int i = 0; i < n; ++i){ for(int x = max(0LL, ax[i] - 300); x < min(ax[i] + 300, 100LL); ++x){ for(int y = max(0LL, ay[i] - 300); y < min(ay[i] + 300, 100LL); ++y){ int dx = x - ax[i]; int dy = y - ay[i]; if(dx * dx + dy * dy <= 100 * 100){ ++points[x][y]; } } } } */ bx = {200, 400, 600, 800}; by = {333, 333, 333, 333, 666, 666, 666, 666}; for(int i = 0; i < 8; ++i){ bx[i] = bx[i % 4]; } /* for(int j = 0; j < 8; ++j){ bool fl = false; while(!fl && points[bx[j]][by[j]] <= 10){ bx[j] = 100 + rnd() % 800; by[j] = 100 + rnd() % 800; fl = true; for(int i = 0; i < j; ++i){ int dx = bx[i] - bx[j]; int dy = by[i] - by[j]; if(sqrt(dx * dx + dy * dy) <= 300){ fl = false; break; } } } } */ vector v(100); iota(v.begin(), v.end(), 0); auto res = tsp(100, v, a_dist, 100); res.emplace_back(0); auto calc_ans = [&](){ vector> ans; ans.emplace_back(0, 0); i64 ds = 0; for(int i = 0; i < n; ++i){ i64 d = dis(0, res[i], 0, res[i + 1]); pair pp(d, -1); for(int j = 0; j < m; ++j){ i64 d2 = dis(0, res[i], 1, j) + dis(1, j, 0, res[i + 1]); chmin(pp, make_pair(d2, j)); } ds += pp.first; if(pp.second != -1){ ans.emplace_back(1, pp.second); } ans.emplace_back(0, res[i + 1]); } return make_pair(ans, ds); }; auto calc_ans_light = [&](){ i64 ds = 0; for(int i = 0; i < n; ++i){ i64 d = dis(0, res[i], 0, res[i + 1]); pair pp(d, -1); for(int j = 0; j < m; ++j){ i64 d2 = dis(0, res[i], 1, j) + dis(1, j, 0, res[i + 1]); chmin(pp, make_pair(d2, j)); } ds += pp.first; } return ds; }; auto calc_sc = [&](i64 dist){ return round(1000000000 / (1000 + sqrt(dist))); }; auto best = calc_ans_light(); auto best_b = make_pair(bx, by); bool fl = true; int itr = 0; constexpr double start_temp = 1;//100000; constexpr double end_temp = 1e-6; constexpr double end_time = 0.9; double per = 0.0; while(fl){ // cout << per << endl; for(int _ = 0; _ < 100; ++_){ double new_per = double(clock() - st) / CLOCKS_PER_SEC / end_time; if(new_per >= 1.0){ fl = false; break; } if(itr && itr % 1000 == 0){ // if(per < 0.3 && new_per >= 0.3){ vector> dist(n, vector(n)); for(int i = 0; i < n; ++i){ for(int j = 0; j < n; ++j){ dist[i][j] = dis(0, i, 0, j); for(int k = 0; k < 8; ++k){ chmin(dist[i][j], dis(0, i, 1, k) + dis(1, k, 0, j)); } } } res = tsp(n, res, dist, 10); res.emplace_back(0); } // per = new_per; ++itr; int idx = rnd() & 7; int px = bx[idx]; int py = by[idx]; int dx, dy; if(rnd() % 5){ dx = rnd() % 300 - 150; dy = rnd() % 300 - 150; bx[idx] += dx; by[idx] += dy; } else{ dx = rnd() % 600 - 300; dy = rnd() % 600 - 300; bx[idx] += dx; by[idx] += dy; } auto now = calc_ans_light(); auto diff = best - now; double temp = start_temp + (end_temp - start_temp) * per; /* if(diff > 0){ cout << diff << endl; } */ // cout << diff << " " << temp << " : " << exp(diff / temp) << endl; // if(exp(diff / temp) >= rnd_double()){ if(diff >= 0){ // cout << points[bx[idx]][by[idx]] << endl; best = now; // cout << calc_sc(best) << endl; best_b = make_pair(bx, by); } else{ bx[idx] = px; by[idx] = py; } } } // cout << itr << endl; tie(bx, by) = best_b; auto ans = calc_ans().first; #ifdef HAND cout << itr << endl; #else for(int i = 0; i < m; ++i){ cout << bx[i] << " " << by[i] << endl; } cout << ans.size() << endl; for(int i = 0; i < ans.size(); ++i){ cout << ans[i].first + 1 << " " << ans[i].second + 1 << endl; } #endif } signed main(){ st = clock(); #ifdef OPTIMIZE params::load_params(); #endif #ifndef HAND read_file(cin); #else ifstream ifs("./tools/in/0001.txt"); assert(ifs.is_open()); read_file(ifs); #endif solve(); }