Задание 27. Информатика. ЕГЭ. Поляков-7652

Просмотры: 415
Изменено: 2 февраля 2025

(В. Ланская, Р. Ягафаров) Шёл 2077 год. Ученому необходимо провести кластеризацию населенных пунктов двух больших районов на картах планет Информатикус и Алгоритмикус. Район (кластер) – это групп населенных пунктов, которые находятся внутри прямоугольника высотой H и шириной W. Каждый населенный пункт обязательно принадлежит только одному району. Столица района (или центроид) – это такой населенный пункт, сумма манхэттенских расстояний от которого до всех других населённых пунктов в кластере минимальна. Манхэттенское расстояние между двумя точками A(x1,y1) и B(x2,y2) вычисляется по формуле: d(A,B)=|x2−x1|+|y2−y1| Даны два входных файла (файл A и файл Б). В файле A хранятся данные о точках двух кластеров. В каждой строке записана информация о расположении одной точки: сначала координата x, затем координата y (в условных единицах). Известно, что количество точек не превышает 1000. В файле Б той же структуры хранятся данные о точках трёх кластеров. Известно, что количество точек не превышает 10 000. Возможные данные одного из файлов иллюстрированы графиком.

Для каждого файла определите координаты центра каждого кластера, затем вычислите два числа: Px – среднее арифметическое абсцисс центров кластеров, и Py – среднее арифметическое ординат центров кластеров. В ответе запишите четыре числа: в первой строке сначала целую часть произведения Px×10 000, затем целую часть произведения Py×10 000 для файла А, во второй строке – аналогичные данные для файла Б.

Файл с данными

Решение:

Точечная диаграмма, построенная для файла А в табличном процессоре, имеет вид

Видно, что кластеры можно разделить, прямой x=−4

Точечная диаграмма для файла Б, построенная в табличном процессоре, имеет вид

Верхний кластер отделяется от остальных прямой y=−4. Нижние разделяются прямой x=−3.

Python (3.10+)


def which_cluster(point, task):
    x, y = point
    match task:
        case 0:
            return int(x > -4)
        case 1:
            if y > -4:
                return 0
            elif x < -3:
                return 1
            else:
                return 2

def dist(point1, point2):
    x1, y1 = point1
    x2, y2 = point2
    return abs(x1 - x2) + abs(y1 - y2)

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

for t in [0, 1]:
    fd = open(base + files[t])
    fd.readline()
    data = [[], [], []]
    for line in fd:
        x, y = map(float, line.replace(',', '.').split())
        data[which_cluster([x, y], t)].append([x, y])
    centers = []
    for k in range(clusters[t]):
        dm = 10**100
        c = [0, 0]
        for p in data[k]:
            d = sum(dist(p, pt) for pt in data[k])
            if d < dm:
                dm = d
                c = p
        centers.append(c)
    px = int(sum(c[0] for c in centers) / clusters[t] * 10000)
    py = int(sum(c[1] for c in centers) / clusters[t] * 10000)
    print(px, py)

Ответ:
−31374   25065
−31622   −49268