import java.io.BufferedReader; import java.io.File; import java.io.FileReader; import java.io.InputStreamReader; import java.io.PrintWriter; import java.util.ArrayList; import java.util.HashSet; import java.util.List; import java.util.PriorityQueue; import java.util.Set; public class Main { static boolean batch = false; static boolean readFile = false; static int num = 0; static long limitTime = 850; static long startTime; static double startTemp = 2000; static double endTemp = 10; static int baseTry = 100; static int baseNum = 7; static int startSeni = 300; static int endSeni = 10; static int a = 5; static int N, M; static Obj[] arr, pln; public static void main(String[] args) throws Exception { if (batch) { readFile = true; } if (readFile) { if (batch) { long tl = 1000; long tw = (long) (tl * 0.9); long total = 0; int bidx = 0; int best = 0; int widx = 0; int worst = 1000000000; int re = 0; int tle = 0; for (int z = 0; z < 30; z++) { try { long st = System.currentTimeMillis(); int score = solve(z); long time = System.currentTimeMillis() - st; if (time > tw) { System.out.println(z + ":\t" + score + "\t" + time + "ms"); if (time > tl) { tle++; } } else { System.out.println(z + ":\t" + score); } total += score; if (score > best) { best = score; bidx = z; } if (score < worst) { worst = score; widx = z; } } catch (Exception e) { System.out.println(z + ":\t" + e.getMessage()); re++; } } System.out.println("total: " + total); System.out.println("best: " + bidx + ": " + best); System.out.println("worst: " + widx + ": " + worst); System.out.println("RE: " + re); System.out.println("TLE: " + tle); } else { int score = solve(num); System.out.println(score); } } else { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); init(br); solve(); } } static int solve(int z) throws Exception { StringBuilder sb = new StringBuilder(); sb.append(z); while (sb.length() < 4) { sb.insert(0, '0'); } File file = new File("G:\\input\\" + sb.toString() + ".txt"); BufferedReader br = new BufferedReader(new FileReader(file)); init(br); return solve(); } static void init(BufferedReader br) throws Exception { startTime = System.currentTimeMillis(); String[] sa = br.readLine().split(" "); N = Integer.parseInt(sa[0]); M = Integer.parseInt(sa[1]); arr = new Obj[N + M]; pln = new Obj[N]; for (int i = 0; i < N; i++) { sa = br.readLine().split(" "); Obj o = new Obj(); o.t = 1; o.i = i; o.x = Integer.parseInt(sa[0]); o.y = Integer.parseInt(sa[1]); pln[i] = o; arr[i] = o; } } static int solve() throws Exception { Ans ans = new Ans(); PriorityQueue que = new PriorityQueue<>((o1, o2) -> o1.score - o2.score); for (int i = 0; i < baseTry; i++) { Ans res = solve2(null, 0); que.add(res); if (que.size() > baseNum) { que.poll(); } if (res.score > ans.score) { ans = res; } } for (Ans o : que) { if (o.score > ans.score) { ans = o; } } int ok = 0; int ng = 0; int upd = 0; while (true) { long time = System.currentTimeMillis() - startTime; if (time > limitTime) { break; } double ratio = (double) time / limitTime; double temp = startTemp * (1 - ratio) + endTemp * ratio; int seni = (int) (startSeni * (1 - ratio) + endSeni * ratio); PriorityQueue wk = new PriorityQueue<>((o1, o2) -> o1.score - o2.score); for (Ans base : que) { Ans res = solve2(base, seni); double prob = Math.exp((res.score - base.score) / temp); if (Math.random() < prob) { wk.add(res); ok++; } else { wk.add(base); ng++; } if (res.score > ans.score) { ans = res; upd++; } } boolean flg = false; for (Ans o : wk) { if (o.score == ans.score) { flg = true; break; } } if (!flg) { wk.add(ans); wk.poll(); } que = wk; } if (!batch) { PrintWriter pw = new PrintWriter(System.out); for (Obj o : ans.sta) { pw.println(o.x + " " + o.y); } pw.println(ans.his.size()); for (int cur : ans.his) { int ct = cur / N; int ci = cur % N; pw.println(ct + " " + (ci + 1)); } if (readFile) { pw.println("ok: " + ok); pw.println("ng: " + ng); pw.println("upd: " + upd); } pw.flush(); } return ans.score; } static Ans solve2(Ans base, int seni) throws Exception { // 宇宙ステーションの配置 Obj[] sta = new Obj[M]; if (base == null) { for (int i = 0; i < M; i++) { Obj o = new Obj(); o.t = 2; o.i = i; o.x = rand(100, 900); o.y = rand(100, 900); while (true) { boolean flg = true; for (int j = 0; j < i; j++) { Obj o2 = sta[j]; if (dist(o, o2) < 200) { flg = false; break; } } if (flg) { break; } o.x = rand(100, 900); o.y = rand(100, 900); } sta[i] = o; arr[N + i] = o; } } else { Obj[] src = base.sta; for (int i = 0; i < M; i++) { Obj o = new Obj(); o.t = 2; o.i = i; o.x = src[i].x; o.y = src[i].y; sta[i] = o; arr[N + i] = o; } int idx = rand(0, M - 1); int dx = rand(-seni, seni); int dy = rand(-seni, seni); Obj o = sta[idx]; o.x = Math.min(Math.max(o.x + dx, 50), 950); o.y = Math.min(Math.max(o.y + dy, 50), 950); } // 最も近い宇宙ステーションを設定 for (Obj o : pln) { o.costs = Integer.MAX_VALUE; for (Obj o2 : sta) { int e = cost(o, o2); if (e < o.costs) { o.costs = e; o.sta = o2; } } } Set rem = new HashSet<>(); for (int i = 1; i < N; i++) { rem.add(i); } List his = new ArrayList<>(); his.add(toInt(pln[0])); Obj now = pln[0]; while (!rem.isEmpty()) { int min = Integer.MAX_VALUE; List nexts = new ArrayList<>(3); for (int i : rem) { min = minCost(now, pln[i], min, nexts); } his.addAll(nexts); int next = his.get(his.size() - 1) % N; now = pln[next]; rem.remove(next); } List nexts = new ArrayList<>(3); minCost(now, pln[0], Integer.MAX_VALUE, nexts); his.addAll(nexts); // 得点計算 int s = 0; int v = his.size(); for (int i = 1; i < v; i++) { int cur = his.get(i); int pre = his.get(i - 1); int e = cost(arr[pre - N], arr[cur - N]); s += e; } int score = (int) Math.round(1000000000 / (1000 + Math.sqrt(s))); Ans ans = new Ans(); ans.sta = sta; ans.his = his; ans.score = score; return ans; } static int minCost(Obj now, Obj o, int min, List nexts) { int d = cost(now, o); if (d < min) { min = d; nexts.clear(); nexts.add(toInt(o)); } d = cost(now, now.sta) + cost(now.sta, o); if (d < min) { min = d; nexts.clear(); nexts.add(toInt(now.sta)); nexts.add(toInt(o)); } d = cost(now, o.sta) + cost(o.sta, o); if (d < min) { min = d; nexts.clear(); nexts.add(toInt(o.sta)); nexts.add(toInt(o)); } d = cost(now, now.sta) + cost(now.sta, o.sta) + cost(now.sta, o); if (d < min) { min = d; nexts.clear(); nexts.add(toInt(now.sta)); nexts.add(toInt(o.sta)); nexts.add(toInt(o)); } return min; } static int dist(Obj o1, Obj o2) { int dx = o1.x - o2.x; int dy = o1.y - o2.y; return dx * dx + dy * dy; } static int cost(Obj o1, Obj o2) { int e = dist(o1, o2); if (o1.t == 1) e *= a; if (o2.t == 1) e *= a; return e; } static int toInt(Obj o) { return o.t * N + o.i; } static int rand(int l, int u) { int d = u - l + 1; int x = (int) (Math.random() * d); return x + l; } static class Obj { int t, i, x, y; Obj sta; int costs; } static class Ans { Obj[] sta; List his; int score; } }