Задание 27. Информатика. ЕГЭ Статград. База. 12.05.2025

Океанограф проводит анализ множества островов по их расположению на карте. Каждый остров задаётся своими координатами \((x, \, y).\) Два острова считаются соседними, если расстояние между ними по формуле Евклида $$d(A, \, B) = \sqrt{(x_2 - x_1)^2 + (y_2 -y_1)^2}$$ строго меньше \(1\) условной единицы. При этом используется следующее определение архипелага и одиночного острова: острова принадлежат одному и тому же архипелагу, если между ними существует цепочка соседних островов (то есть, для любой пары островов \(A\) и \(B\) в архипелаге можно найти последовательность \(A = P_1, \, P_2, \, \ldots , \, P_k = B,\) где расстояние между соседними островами \(P_i\) и \(P_{i+1}\) меньше \(1).\) Архипелагом считается только такое объединение островов, в котором общее количество островов не менее \(20.\) Если какая-либо группа островов, связанная по вышеописанному принципу, содержит менее \(20\) островов, она не рассматривается как архипелаг, а все входящие в неё острова считаются одиночными и не учитываются в дальнейшем анализе.

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

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

В ответе запишите четыре числа: в первой строке – целые части абсолютных значений произведений \(M_x \times 10~000\) и \(M_y \times 10~000\) для файла A. Во второй строке – целые части абсолютных значений произведений \(M_x \times 10~000\) и \(M_y \times 10~000\) для файла B.

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

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

from math import dist

files = ['27A.txt', '27B.txt']

for task in (0, 1):
    data = [tuple(float(z) for z in 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) < 1]
            clusters[-1] += neigh
            for pt in neigh:
                data.remove(pt)
    #print(len(clusters), [len(c) for c in clusters])
    clusters = [c for c in clusters if len(c) > 19]
    #print(len(clusters), [len(c) for c in clusters])
    anti_dist = 0
    M = (0, 0)
    for cl in clusters:
        dmax = 0
        c = (0, 0)
        for p in cl:
            d = sum(dist(p, pt) for pt in cl)
            if d > dmax:
                dmax = d
                c = p
        if dmax > anti_dist:
            anti_dist = dmax
            M = c
        Mx, My = M
    print(int(abs(Mx * 10_000)), int(abs(My * 10_000)))