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

(Д. Бахтиев) Учёный наблюдает проекцию звёздного скопления на плоскость с декартовой системой координат. Полученные точки (звёзды) необходимо разбить на \(N\) непересекающихся непустых кластеров. Каждый кластер размещается внутри прямоугольника размером \(H \times W,\) при этом прямоугольники не перекрываются. Стороны прямоугольников не обязаны быть параллельны осям координат. Гарантируется, что такое разбиение единственно для заданных размеров прямоугольников. Расстояние между двумя точками \(A(x_1, \, y_1)\) и \(B(x_2, \, y_2)\) вычисляется по формуле: $$ A(x_1, \, y_1) = \sqrt{(x_2 - y_1)^2 + (y_2 - y_1)^2} $$ Центром кластера будем называть точку кластера, сумма расстояний от которой до остальных точек этого кластера минимальна. Антицентром кластера будем называть точку кластера, сумма расстояний от которой до остальных точек этого кластера максимальна.

Входные данные

Файл A: содержит координаты звёзд, расположенных в \(2\) кластерах, размеры кластеров \(H = 5,\) \(W = 4,\) не более \(1000\) точек.

Файл В: содержит координаты звёзд в \(3\) кластерах, размеры кластеров \(H = 4,\) \(W =5,\) не более \(10~000\) точек.

Каждая строка файлов A и B содержит два числа — координаты звезды: сначала по оси \(x,\) затем по оси \(y.\)

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

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

Возможные данные одного из файлов иллюстрированы графиком.

Внимание! График приведён в иллюстративных целях для произвольных значений, не имеющих отношения к заданию.

Для выполнения задания используйте данные из прилагаемого файла.

from math import dist

files = ['27A.txt', '27B.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])
    centers = []
    anticenters = []
    for cl in clusters:
        dmin = 10**100
        dmax = 0
        c = None
        ac = None
        for p in cl:
            d = sum(dist(p, pt) for pt in cl)
            if d < dmin:
                dmin = d
                c = p
            if d > dmax:
                dmax = d
                ac = p
        centers.append(c)
        anticenters.append(ac)
    Px = sum(c[0] for c in centers) / len(centers)
    Sy = sum(ac[1] for ac in anticenters) / len(anticenters)
    print(abs(int(Px * 10000)), abs(int(Sy * 10000)))