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

(Д. Бахтиев) Компания «СвязьЛес» разрабатывает проект по обеспечению бесперебойной связи в двух труднодоступных лесных массивах. Для этого необходимо установить по одному мощному ретранслятору сигнала в каждом из районов, в местах, где их воздействие будет максимальным. Каждый район состоит из множества лесных участков, представленных в виде геопозиций — точек на плоскости (в декартовой системе координат). Известно, что участки можно разделить на группы лесных кварталов, при этом каждая геопозиция квартала удалена от всех точек других кварталов не менее чем на \(R\) условных единиц.

Компания «СвязьЛес» проводит анализ каждой группы (лесного квартала) и выбирает в ней антицентроид — такую геопозицию, сумма расстояний от которой до всех других точек этого квартала максимальна. После этого, опираясь на данные о расположении всех антицентроидов, выбирается финальная точка установки ретранслятора — такая геопозиция, сумма расстояний от которой до всех антицентроидов максимальна. Именно здесь устанавливается ретранслятор.

Расстояние между двумя точками вычисляется по формуле Евклида: \(d = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}.\)

В файле А хранятся данные обо всех геопозициях первого района. В первой строке записано значение \(R\) для этого района. В каждой из следующих строк записана информация о расположении в районе одной геопозиции: сначала координата \(x,\) затем координата \(y.\) Значения даны в условных единицах, которые представлены вещественными числами. Известно, что количество геопозиций не превышает \(2000.\) В файле Б хранятся данные обо всех геопозициях второго района. В первой строке записано значение \(R\) для этого района. Известно, что количество геопозиций не превышает \(10~000.\) Структура хранения информации в файле Б аналогична файлу А.

Для каждого файла выведите координаты точки установки ретранслятора. В ответе запишите четыре числа: в первой строке сначала целую часть модуля произведения координаты \(x\) этой геопозиции на \(10000,\) затем целую часть модуля произведения координаты \(y\) этой геопозиции на \(10000\) для файла А, во второй строке — аналогичные данные для файла Б.

from math import dist

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

for task in (0, 1):
    fd = open(base + files[task])
    R = float(fd.readline())
    data = [tuple(map(float, line.split())) for line in fd]
    clusters = []
    while data:
        clusters.append([data.pop()])
        for p in clusters[-1]:
            neigh = [pt for pt in data if dist(p, pt) < R]
            clusters[-1] += neigh
            for pt in neigh:
                data.remove(pt)
    #print(len(clusters), [len(c) for c in clusters])
    cent = []
    c = None
    for cl in clusters:
        dmax = 0
        for p in cl:
            d = sum(dist(p, pt) for pt in cl)
            if d > dmax:
                dmax = d
                c = p
        cent.append(c)
    dmax = 0
    retr = None
    for cl in clusters:
        for p in cl:
            d = sum(dist(p, x) for x in cent)
            if d > dmax:
                dmax = d
                retr = p
    print(abs(int(retr[0] * 10000)), abs(int(retr[1] * 10000)))