import itertools import random import time start = time.time() N, M = map(int, input().split()) AB = [list(map(int, input().split())) for _ in range(N)] class KMeans: def __init__(self, n_clusters, max_iter = 10, random_seed = 0): self.n_clusters = n_clusters self.max_iter = max_iter def fit(self, X): self.labels_ = [] now = 0 while len(self.labels_) < len(X): self.labels_.append(now) now += 1 now %= self.n_clusters random.shuffle(self.labels_) labels_prev = [0]*len(X) count = 0 self.cluster_centers_ = [(0, 0)] * self.n_clusters while (not (self.labels_ == labels_prev) and count < self.max_iter): syuukei = [[] for _ in range(self.n_clusters)] for i in range(len(X)): syuukei[self.labels_[i]].append(X[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 = random.randint(0, 1000), random.randint(0, 1000) self.cluster_centers_[i] = (x, y) labels_prev = self.labels_[:] for i in range(len(X)): dist = 10**18 for j in range(self.n_clusters): tmp = (X[i][0] - self.cluster_centers_[j][0])**2 + (X[i][1] - self.cluster_centers_[j][1])**2 if tmp < dist: dist = tmp self.labels_[i] = j count += 1 def main(): model = KMeans(8) model.fit(AB) labels = model.labels_ centers = model.cluster_centers_ def dist(a, b): return (a[0] - b[0])**2 + (a[1] - b[1])**2 def calc(ans): 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]) if type_pre == 1 and type_now == 2: score += 5*dist(AB[indx_pre], centers[indx_now]) if type_pre == 2 and type_now == 1: score += 5*dist(centers[indx_pre], AB[indx_now]) if type_pre == 2 and type_now == 2: score += 1*dist(centers[indx_pre], centers[indx_now]) return score vest = 1<<30 ANS = [] L = [[] for _ in range(8)] for i, cluster_number in enumerate(labels): L[cluster_number].append(i) for p in itertools.permutations(range(8)): ans = [(1, 0)] for i in p: if i >= len(L): continue ans.append((2, i)) lim = len(L[i]) j = 0 while j < lim: 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)) j += 1 ans.append((1, 0)) score = calc(ans) if score < vest: vest = score ANS = ans[:] return vest, ANS, centers ANS = [] CENTERS = [] vest = 1<<30 while time.time() - start < 0.5: tmp, ans, centers = main() if tmp < vest: vest = tmp ANS = ans[:] CENTERS = centers for c,d in CENTERS: print(c, d) print(len(ANS)) for a,b in ANS: print(a, b+1)