Задача #2929

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

Уровень ЕГЭ

(В. Лашин) Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на N непересекающихся непустых подмножеств (кластеров), таких что точки каждого подмножества лежат внутри прямоугольника со сторонами длиной H и W, причём эти прямоугольники между собой не пересекаются. Стороны прямоугольников не обязательно параллельны координатным осям.
Гарантируется, что такое разбиение существует и единственно для заданных размеров прямоугольников.

Будем называть диагональю кластера такой отрезок, что образующие его две точки кластера максимально отдалены друг от друга. Гарантируется единственной такой пары точек в кластере. Расстояние между двумя точками на плоскости A(x1,y1) и B(x2,y2) вычисляется по формуле: $d (A, B) = \sqrt{(x_{1} - x_{2})^{2} + (y_{1} - y_{2})^{2}}$

В файле A хранятся данные о звёздах двух кластеров, где H=3, W=3 для каждого кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата x, затем координата y. Значения даны в условных единицах. Известно, что количество звёзд не превышает 1000. В файле B хранятся данные о звёздах трёх кластеров, где H=3, W=3 для каждого кластера. Известно, что количество звёзд не превышает 10 000. Структура хранения информации о звездах в файле B аналогична файлу А. Для каждого файла определите координаты точек образующих диагональ каждого кластера, затем вычислите два числа: Px – среднее арифметическое абсцисс образующих диагонали точек кластеров, и Py – среднее арифметическое ординат образующих диагонали точек кластеров. В ответе запишите четыре числа: в первой строке сначала целую часть произведения Px×10000, затем целую часть произведения Py×10000 для файла А, во второй строке – аналогичные данные для файла B.
Возможные данные одного из файлов иллюстрированы графиком.

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

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

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

Вопрос A

Вопрос B

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

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

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

Ответ

Вопрос A

16730

48696

Вопрос B

23982

47539

from math import *


def d(claster):
    mx = 0
    points = []
    for point1 in claster:
        for point2 in claster:
            if dist(point1, point2) > mx:
                mx = dist(point1, point2)
                points = [point1, point2]
    return points


clasters = []
for point in open('27B_20130.txt'):
    point = list(map(float, point.replace(',', '.').split()))
    clasters.append([point])
    for claster in clasters[:-1]:
        if any(dist(point, point_claster) < 1 for point_claster in claster):
            clasters[-1] += claster
            clasters.remove(claster)
ds = [d(claster) for claster in clasters]
# print(len(ds)) проверка правильности выделения кластеров
print(abs(int(sum(opor[0][0] + opor[1][0] for opor in ds) / (len(ds) * 2) * 10000)), end=' ')
print(abs(int(sum(opor[0][1] + opor[1][1] for opor in ds) / (len(ds) * 2) * 10000)))

Номер