def greedy(cities,current_city,dist): N = len(cities) unvisited_cities = set(range(0, N)) tour = [current_city] unvisited_cities.remove(current_city) while unvisited_cities: next_city = min(unvisited_cities, key=lambda city: dist[current_city][city]) unvisited_cities.remove(next_city) tour.append(next_city) current_city = next_city return tour,dist def two_opt(tour, dist): N = len(tour) while True: count = 0 for i in range(N-2): for j in range(i+2, N): l1 = dist[tour[i]][tour[i + 1]] l2 = dist[tour[j]][tour[(j + 1) % N]] l3 = dist[tour[i]][tour[j]] l4 = dist[tour[i + 1]][tour[(j + 1) % N]] if l1 + l2 > l3 + l4: new_tour = tour[i+1 : j+1] tour[i+1 : j+1] = new_tour[::-1] count += 1 if count == 0: break return tour def calc_dist(planet, i, j): p1 = planet[i] p2 = planet[j] D = (p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2 return D def calc_dist_from_tour(planet, tour): N = len(tour) dist = list() for i in range(N-1): dist.append([calc_dist(planet, tour[i], tour[i+1]), [tour[i], tour[i+1]]]) return dist # ==================== N, M = map(int, input().split()) planet = [tuple(list(map(int, input().split())) + [1, i]) for i in range(N)] dist = [[0 for _ in range(N)] for _ in range(N)] for i in range(N): for j in range(N): dist[i][j] = calc_dist(planet, i, j) tour, dis = greedy(planet, 0, dist) tour = two_opt(tour, dis) + [1] # distanceの長いところの真ん中らへんに宇宙ステーションを作りたい。 # その後もう一回TSPを回して、焼きなましをして、TSPを回して、・・・ long_dist = calc_dist_from_tour(planet, tour) long_dist.sort(reverse=True) k = M stations = [] for i in range(k): p1, p2 = long_dist[i][1][0], long_dist[i][1][1] stations.append(((planet[p1][0] + planet[p2][0]) // 2, (planet[p1][1] + planet[p2][1]) // 2, 2, i)) visit = stations + planet dista = [[0 for _ in range(len(visit))] for _ in range(len(visit))] for i in range(len(visit)): for j in range(len(visit)): dista[i][j] = calc_dist(visit, i, j) start_num = -1 for i in range(len(visit)): if visit[i][2] == 1 and visit[i][3] == 0: start_num = i tour, dis = greedy(visit, start_num, dista) tour = two_opt(tour, dis) # output for i in range(M):print(*stations[i][:2]) print(len(visit)+1) for i in range(len(tour)): if visit[tour[i]][2] == 1: print(1, visit[tour[i]][3] + 1) else: print(2, visit[tour[i]][3] + 1) print(1, 1)