Задача #3546

Анализ данных

Уровень ЕГЭ

(Лысенков О.) В канун Хэллоуина 2025 года старейшины Гильдии охотников на монстров планирует напасть на жителей заколдованных земель. Для этого они составили мрачную карту, но им мало мрачной карты, им необходимо найти замки на этой карте, так как главная цель уничтожения каждого из замков. Так как Гильдия охотников в первую очередь специализируется на охоте, то у них возникли проблемы с определением замков, но разведать координаты замков с воздуха(именно так они определяли объекты, находящиеся на территории заколдованных земель) невозможно, так как с него все пункты похожие. Именно поэтому, охотники попросили вас помочь им.

Вам была передана следующая информация: на мрачной карте заколдованных земель расположены несколько заброшенных городов-призраков. Каждому городу соответствует свой замок— особая точка, которая скрыта в его районе, и которая считается центром зловещей силы. Каждый город представлен на карте, как набор точек, каждая из которых представляет какие-то важные части города. Известно, что замок(центроид) - такая точка, сумма манхэттенских расстояний от которой до всех других населённых пунктов в кластере минимальна. Манхэттенское расстояние между двумя точками A(x₁, y₁) и B(x₂, y₂) вычисляется по формуле:

$d (A, B) = | x_{2} - x_{1} | + | y_{2} - y_{1} |$

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

Файлы к задаче

Скачать 27A.txt Скачать 27B.txt

Вопрос A

Вопрос B

Введите ответ

Войдите, чтобы история ответов и статистика сохранялись.

Решение Нажми, чтобы открыть

Ответ

Вопрос A

101666

39433

Вопрос B

131555

134793

Видео по задаче

Смотреть в VK


data = []

for s in open(r"C:\Users\Junkyuosha\Desktop\27B.txt"):
    x,y = [float(d) for d in s.split()]
    data.append([x,y])

def dist(p1,p2):
    x1,y1 = p1
    x2,y2 = p2
    return (abs(x2 - x1) + abs(y2 - y1))

clusters = []
while data:
    cl = [data.pop()]
    for p in cl:
        sosed = [p1 for p1 in data if dist(p,p1) < 4]
        for p1 in sosed:
             cl.append(p1)
             data.remove(p1)
    clusters.append(cl)

clusters = [cl for cl in clusters if len(cl) > 20]
print([len(cl) for cl in clusters])


from turtle import *
from random import  *
screensize(5000,5000)
tracer(0)
up()
for cl in clusters:
    color = random(),random(),random()
    for x,y in cl:
        goto(x * 20, y * 20)
        dot(3,color)
update()
def centroid(cl):
    m = []
    for p in cl:
        s = 0
        for p1 in cl:
            s += dist(p,p1)
        m.append([s,p])
    return min(m)[1]
cen = [centroid(cl) for cl in clusters] #массив центров
px = sum(x for x,y in cen) / len(cen)
py = sum(y for x,y in cen) / len(cen)
print(abs(int(px * 10_000)), abs(int(py * 10_000)))
done()

Номер