from itertools import permutations import sys import random import time import math input = lambda: sys.stdin.readline().rstrip() random.seed(0) START_TIME = time.time() N, M = map(int, input().split()) AB = [list(map(int, input().split())) for _ in range(N)] def fit(): labels_ = [] now = 0 while len(labels_) < N: labels_.append(now) now += 1 if now == 8: now = 0 random.shuffle(labels_) cluster_centers_ = [(0, 0) for _ in range(8)] for _ in range(10): syuukei = [[] for _ in range(8)] for i in range(N): syuukei[labels_[i]].append(AB[i]) for i,l in enumerate(syuukei): if l: x, y = sum(x for x,y in l)//len(l), sum(y for x,y in l)//len(l) else: x, y = 1<<30, 1<<30 x, y = random.randint(0, 1000), random.randint(0, 1000) cluster_centers_[i] = [x, y] for i in range(N): dist = 1<<30 for j in range(8): tmp = (AB[i][0] - cluster_centers_[j][0])**2 + (AB[i][1] - cluster_centers_[j][1])**2 if tmp < dist: dist = tmp labels_[i] = j return labels_, cluster_centers_ def dist(a, b): return (a[0] - b[0])**2 + (a[1] - b[1])**2 def make_ans(): labels, centers = fit() ANS = [] L = [[] for _ in range(8)] for i, cluster_number in enumerate(labels): L[cluster_number].append(i) vest_p = None vest = 1<<30 for p in permutations(range(8)): score = dist((AB[0]), centers[p[0]]) for i in range(len(centers)-1): score += dist(centers[p[i]], centers[p[i+1]]) score += dist(centers[p[-1]], AB[0]) if score < vest: vest = score vest_p = p[:] if time.time() - START_TIME > 0.9: return 1<<30, -1, -1 ans = [(1, 0)] for i in vest_p: if i >= len(L): continue ans.append((2, i)) for j in range(len(L[i])): d1 = 5 * dist(AB[L[i][j]], centers[i]) d2 = 1<<30 if j+1 < len(L[i]): d2 = 25* dist(AB[L[i][j]], AB[L[i][j+1]]) if d2 < d1: ans.append((1, L[i][j])) else: ans.append((1, L[i][j])) ans.append((2, i)) ans.append((1, 0)) score = 0 for i in range(len(ans)-1): type_pre, indx_pre = ans[i] type_now, indx_now = ans[i+1] if type_pre == 1 and type_now == 1: score += 25*dist(AB[indx_pre], AB[indx_now]) elif type_pre == 1 and type_now == 2: score += 5*dist(AB[indx_pre], centers[indx_now]) elif type_pre == 2 and type_now == 1: score += 5*dist(centers[indx_pre], AB[indx_now]) elif type_pre == 2 and type_now == 2: score += dist(centers[indx_pre], centers[indx_now]) return round(10**9 / (1000 + score**.5)), ans, centers def main(): ANS = [] CENTERS = [] FINAL_VESTSCORE = 0 # ====================== # 初期解生成 cnt = 0 while time.time() - START_TIME < 0.6: cnt += 1 score, ans, centers = make_ans() if score > FINAL_VESTSCORE: FINAL_VESTSCORE = score ANS = ans[:] CENTERS = centers # print(score, file=sys.stderr) # print(cnt, file=sys.stderr) # ====================== def debug(*args): print(*args, file=sys.stderr) # ====================== # 焼きなまし def modify(centers): i = random.randint(0, 7) d1 = random.randint(-5, 5) d2 = random.randint(-5, 5) centers[i][0] += d1 centers[i][1] += d2 if centers[i][0] < 0: centers[i][0] = 0 if centers[i][1] < 0: centers[i][1] = 0 if centers[i][0] > 1000: centers[i][0] = 1000 if centers[i][1] > 1000: centers[i][1] = 1000 return centers def calc(new_centers): score = 0 for i in range(len(ANS)-1): type_pre, indx_pre = ANS[i] type_now, indx_now = ANS[i+1] if type_pre == 1 and type_now == 1: score += 25*dist(AB[indx_pre], AB[indx_now]) elif type_pre == 1 and type_now == 2: score += 5*dist(AB[indx_pre], new_centers[indx_now]) elif type_pre == 2 and type_now == 1: score += 5*dist(new_centers[indx_pre], AB[indx_now]) elif type_pre == 2 and type_now == 2: score += dist(new_centers[indx_pre], new_centers[indx_now]) return round(10**9 / (1000 + score**.5)) START_TEMP, END_TEMP = 1000, 10 TIME_LIMIT = 0.85 FINAL_CENTERS = CENTERS[:] vestscore = FINAL_VESTSCORE cnt = 0 while time.time() - START_TIME < TIME_LIMIT: cnt += 1 new_centers = modify(CENTERS[:]) new_score = calc(new_centers) temp = START_TEMP + (END_TEMP - START_TEMP) * (time.time() - START_TIME) / TIME_LIMIT prob = math.exp((new_score - vestscore) / temp) if prob > random.random(): vestscore = new_score CENTERS = [c[:] for c in new_centers] if new_score > FINAL_VESTSCORE: FINAL_VESTSCORE = new_score FINAL_CENTERS = [c[:] for c in new_centers] # debug('cnt', cnt) # ====================== for c, d in FINAL_CENTERS: print(c, d) print(len(ANS)) for a, b in ANS: print(a, b+1) debug(FINAL_VESTSCORE) main()