Задание 27. Информатика. ЕГЭ. Шастин. 9.2.2025

(Д. Бахтиев) Учёный решил провести кластеризацию множества звёзд по их расположению на карте звёздного неба. Каждая звезда задаётся своими координатами \((x, \, y).\) Две звезды считаются соседними, если расстояние между ними по формуле Евклида $$ d(A, \, B) = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2} $$ строго меньше \(1\) условной единицы.

При этом используется следующее определение кластера и аномалии: звезды принадлежат одному и тому же кластеру, если между ними существует цепочка соседних звёзд (то есть, для любой пары звёзд \(A\) и \(B\) в кластере можно найти последовательность $$ A = P_1, \, P_2, \, \ldots , P_k = B, $$ где расстояние между соседними звёздами \(P_i\) и \(P_{i+1}\) меньше \(1\)). При этом кластером считается только такое объединение звёзд, в котором общее число точек не менее \(20.\) Если какая-либо группа звёзд, связанная по вышеописанному принципу, содержит менее \(20\) точек, она не рассматривается как кластер, а все входящие в неё звёзды считаются аномалиями.

Входные данные задаются в двух файлах: файл \(A\) и файл \(B.\) В каждой строке файлов содержатся координаты звёзд: сначала по оси \(x,\) затем по оси \(y.\) При условии, что аномалии при расчётах игнорируются, требуется определить координаты центроида самого маленького (по числу звёзд) кластера. Центроид кластера определяется как звезда, принадлежащая кластеру, для которой сумма расстояний до всех остальных звёзд этого кластера минимальна. Гарантируется, что такой кластер определяется однозначно. В ответе запишите четыре числа: в первой строке для файла \(A\) результаты произведений \(C_x \cdot 10000\) и \(C_y \cdot 10000,\) где \(C_x\) и \(C_y\) — координаты центроида кластера по осям \(x\) и \(y\) соответственно, а во второй строке аналогичные данные для файла \(B.\)

from math import dist

base = ''
files = ['27_A.txt', '27_B.txt']

for task in (0, 1):
    data = [tuple(map(float, line.split())) for line in open(base + files[task])]
    clusters = []
    eps = 1
    while data:
        clusters.append([data.pop(0)])
        for p in clusters[-1]:
            neigh = [p1 for p1 in data if dist(p, p1) < eps]
            clusters[-1] += neigh
            for p1 in neigh:
                data.remove(p1)
    #print(len(clusters), [len(c) for c in clusters])
    clusters = sorted([cl for cl in clusters if len(cl) > 19], key=lambda c: len(c))
    #print(len(clusters[0]))
    dmax = float('inf')
    cx, cy = 0, 0
    for p in clusters[0]:
        d = sum(dist(p, pt) for pt in clusters[0])
        if d < dmax:
            dmax = d
            cx, cy = p
    print(round(cx * 10000), round(cy * 10000))