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

(Д. Бахтиев) Во время геофизического исследования был построен план подземного участка местности. На карте, спроецированной на плоскость с декартовой системой координат, отмечены сигналы, полученные от различных объектов. Каждая точка на карте соответствует зарегистрированному сигналу с координатами \(x\) и \(y\) (в условных единицах).

Учёный решил провести кластеризацию этих сигналов, то есть разбить их множество на \(N\) непересекающихся непустых подмножеств (кластеров). Гарантируется, что такое разбиение существует и единственно.

Будем называть центром кластера такую его точку, сумма расстояний от которой до всех остальных точек кластера минимальна. Расстояние между двумя точками на плоскости \(A(x_1, \, y_1)\) и \(B(x_2, \, y_2)\) вычисляется по формуле: $$d = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}.$$ В процессе анализа выяснилось, что среди сигналов присутствуют аномальные шумы. Это — ложные сигналы, вызванные помехами. Известно следующее:

• Учёный не знает координат аномалий заранее;
• Однако он знает, что:
  • Аномалии не принадлежат ни одному кластеру
  • Для любой пары настоящих точек одного кластера можно найти последовательность \(A = P_1, \, P_2, \, \ldots , P_k = B,\) где расстояние между соседними сигналами \(P_i\) и \(P_{i+1}\) меньше \(1.\)
  • В единичной окрестности любой настоящей точки нет ни одной аномальной;
  • В любом кластере более \(5\) точек;
  • Количество аномалий не более \(20\) для каждого из файлов.

Входные данные задаются в двух файлах: файл A и файл B. В каждой строке файлов записана информация о расположении на карте одного сигнала или аномалии: сначала координата \(x,\) затем координата \(y.\) Значения даны в условных единицах. Известно, что количество записей не превышает \(1000\) для файла A и \(10000\) для файла B.

Для каждого файла определите координаты центра каждого кластера, затем вычислите два числа: \(P_x\) — среднее арифметическое абсцисс центров кластеров, и \(P_y\) — среднее арифметическое ординат центров кластеров.

В ответе запишите четыре числа: в первой строке сначала целую часть абсолютно значения произведения \(P_x \times 10000,\) затем целую часть абсолютного значения произведения \(P_y \times 10000\) для файла A, во второй строке — аналогичные данные для файла B.

from math import dist

files = ['27A_22624.txt', '27B_22624.txt']
eps = 1

for task in (0, 1):
    data = [tuple(map(float, line.split())) for line in open(files[task])]
    clusters = []
    while data:
        clusters.append([data.pop()])
        for p in clusters[-1]:
            neigh = [pt for pt in data if dist(p, pt) < eps]
            clusters[-1] += neigh
            for pt in neigh:
                data.remove(pt)
    #print(len(clusters), [len(cl) for cl in clusters])
    clusters = [cl for cl in clusters if len(cl) > 5]
    #print(len(clusters), [len(cl) for cl in clusters])
    centers = []
    for cl in clusters:
        dmin = float('inf')
        c = None
        for p in cl:
            d = sum(dist(p, pt) for pt in cl)
            if d < dmin:
                dmin = d
                c = p
        centers.append(c)
    px = sum(c[0] for c in centers) / len(centers)
    py = sum(c[1] for c in centers) / len(centers)
    print(abs(int(px * 10_000)), abs(int(py * 10_000)))