#include // デバッグ用マクロ:https://naskya.net/post/0002/ #ifdef LOCAL #include #define debug(...) debug_print::multi_print(#__VA_ARGS__, __VA_ARGS__) #else #define debug(...) (static_cast(0)) #endif using namespace std; using namespace chrono; using ll = long long; using vi = vector; using vl = vector; using vs = vector; using vc = vector; using vb = vector; using vpii = vector>; using vpll = vector>; using vvi = vector>; using vvl = vector>; using vvc = vector>; using vvb = vector>; using vvvi = vector>>; using pii = pair; // #include // using namespace atcoder; #define rep(i, n) for (int i = 0; i < (int)(n); i++) #define all(x) (x).begin(), (x).end() // #define MAX 10000 #define INFTY (1 << 30) // 浮動小数点の誤差を考慮した等式 #define EPS (1e-10) #define equal(a, b) (fabs((a) - (b)) < EPS) template inline bool chmax(T &a, T b) { return ((a < b) ? (a = b, true) : (false)); } template inline bool chmin(T &a, T b) { return ((a > b) ? (a = b, true) : (false)); } // 焼きなまし法の参考にしたページ // https://shindannin.hatenadiary.com/entry/2021/03/06/115415 // 0以上UINT_MAX(0xffffffff)以下の整数をとる乱数 xorshift // https://ja.wikipedia.org/wiki/Xorshift static uint32_t randXor() { static uint32_t x = 123456789; static uint32_t y = 362436069; static uint32_t z = 521288629; static uint32_t w = 88675123; uint32_t t; t = x ^ (x << 11); x = y; y = z; z = w; return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)); } // 0以上1未満の小数をとる乱数 static double rand01() { return (randXor() + 0.5) * (1.0 / UINT_MAX); } struct Solver { int N, M; vi a, b; // α int A = 5; vpii stupidInit() { vpii ret; rep(i, N) ret.emplace_back(1, i + 1); ret.emplace_back(1, 1); return ret; } // 惑星を経由しない vpii greedyInit() { vpii ret; vector distList(N); auto dist = [](int x1, int y1, int x2, int y2) { return (ll)((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)); }; rep(i, N) rep(j, i) { int x1 = a[i]; int y1 = b[i]; int x2 = a[j]; int y2 = b[j]; auto d = A * A * dist(x1, y1, x2, y2); distList[i].emplace_back(d, j); distList[j].emplace_back(d, i); } rep(i, N) sort(all(distList[i])); vi color(N); int now = 0; color[0] = 1; ret.emplace_back(1, 1); rep(i, N) { for (auto p : distList[now]) { if (color[p.second]) continue; now = p.second; color[p.second] = 1; ret.emplace_back(1, now + 1); break; } } ret.emplace_back(1, 1); return ret; } // 惑星を経由する vpii greedyInit2(vpii &cd) { vpii ret; vector distList(N); map mp; auto dist = [&](int x1, int y1, int x2, int y2, int xi, int yi) { vpii value; ll dt = A * A * (ll)((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)); rep(i, (int)cd.size()) { auto x = cd[i].first; auto y = cd[i].second; ll tmp = A * (ll)((x1 - x) * (x1 - x) + (y1 - y) * (y1 - y)); tmp += A * (ll)((x - x2) * (x - x2) + (y - y2) * (y - y2)); if (chmin(dt, tmp)) { value.clear(); value.emplace_back(2, i + 1); } } ll tmp1 = INFTY; ll tmp2 = INFTY; int idx1, idx2; rep(i, (int)cd.size()) { auto x = cd[i].first; auto y = cd[i].second; if (chmin(tmp1, A * (ll)((x1 - x) * (x1 - x) + (y1 - y) * (y1 - y)))) idx1 = i; if (chmin(tmp2, A * (ll)((x1 - x) * (x1 - x) + (y1 - y) * (y1 - y)))) idx2 = i; } if (idx1 != idx2) { auto xx1 = cd[idx1].first; auto yy1 = cd[idx1].first; auto xx2 = cd[idx2].first; auto yy2 = cd[idx2].first; ll tmp3 = (ll)((xx1 - xx2) * (xx1 - xx2) + (yy1 - yy2) * (yy1 - yy2)); if (chmin(dt, tmp1 + tmp2 + tmp3)) { value.clear(); value.emplace_back(2, idx1 + 1); value.emplace_back(2, idx2 + 1); } } mp[make_pair(xi, yi)] = value; return dt; }; rep(i, N) rep(j, i) { int x1 = a[i]; int y1 = b[i]; int x2 = a[j]; int y2 = b[j]; auto d = A * A * dist(x1, y1, x2, y2, i, j); mp[make_pair(j, i)] = mp[make_pair(i, j)]; distList[i].emplace_back(d, j); distList[j].emplace_back(d, i); } rep(i, N) sort(all(distList[i])); vi color(N); int now = 0; color[0] = 1; ret.emplace_back(1, 1); rep(i, N) { for (auto p : distList[now]) { if (color[p.second]) continue; for (auto pp : mp[make_pair(now, p.second)]) { ret.push_back(pp); } ret.emplace_back(1, p.second + 1); now = p.second; color[p.second] = 1; break; } } ret.emplace_back(1, 1); return ret; } // 宇宙ステーションの初期配置 vpii initStation() { vpii ret; ret.emplace_back(800, 500); ret.emplace_back(200, 500); ret.emplace_back(500, 800); ret.emplace_back(500, 200); ret.emplace_back(600, 600); ret.emplace_back(600, 400); ret.emplace_back(400, 600); ret.emplace_back(400, 400); return ret; } // シンプルなスコア計算 ll calcScore(vpii &tr) { ll ret = 0; int len = (int)tr.size(); auto dist = [](int x1, int y1, int x2, int y2) { return (ll)((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)); }; rep(i, len - 1) { if (tr[i].first == 1 && tr[i + 1].first == 1) { int x1 = a[tr[i].second - 1]; int y1 = b[tr[i].second - 1]; int x2 = a[tr[i + 1].second - 1]; int y2 = b[tr[i + 1].second - 1]; ret += A * A * dist(x1, y1, x2, y2); } else if (tr[i].first == 2 && tr[i + 1].first == 2) { // TODO } else { // TODO } } return ret; } void solve() { /* 時間計測 */ auto startClock = system_clock::now(); /* input */ cin >> N >> M; a.resize(N); b.resize(N); rep(i, N) cin >> a[i] >> b[i]; /* solve */ // 初期設定 vpii cd = initStation(); // vpii tr = stupidInit(); // vpii tr = greedyInit(); vpii tr = greedyInit2(cd); // debug(calcScore(tr)); auto maxScore = calcScore(tr); /* 焼きなまし法 */ const static double START_TEMP = 1500; // 開始時の温度 const static double END_TEMP = 100; // 終了時の温度 const static double END_TIME = 0.8; // 終了時間(秒) double time = 0.0; // 経過時間(秒) // ループ回数のデバッグ用 ll cnt = 0; // 答え用 do { cnt++; // 進捗。開始時が0.0で、終了時が1.0 const double progressRatio = time / END_TIME; const double temp = START_TEMP + (END_TEMP - START_TEMP) * progressRatio; // 初挑戦 // バックアップ vpii oldCd = cd; // ランダム変更 int d = randXor() % 8; int dx = randXor() % 100; int dy = randXor() % 100; cd[d].first = (cd[d].first + dx) % 1000; cd[d].second = (cd[d].second + dy) % 1000; // スコア計算 vpii nowTr = greedyInit2(cd); double nowScore = calcScore(nowTr); debug(nowScore, maxScore); if (nowScore <= maxScore) { maxScore = nowScore; tr.clear(); tr = nowTr; } else { cd = oldCd; } // 時間更新 time = ((double)duration_cast(system_clock::now() - startClock) .count() * 1e-6); } while (time < END_TIME); /* output */ debug(cnt); int V = (int)tr.size(); assert(tr[0].second == 1); assert(tr[V - 1].second == 1); rep(i, M) cout << cd[i].first << " " << cd[i].second << "\n"; cout << V << endl; rep(i, V) cout << tr[i].first << " " << tr[i].second << "\n"; } }; int main() { int ts = 1; rep(ti, ts) { Solver solver; solver.solve(); } return 0; }