Задача #2930

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

Уровень ЕГЭ

(В. Лашин) Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на 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_1.txt Скачать 27B_1.txt

Вопрос A

Вопрос B

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

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

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

Ответ

Вопрос A

51428

45632

Вопрос B

28289

38015

from math import dist

clasters = []
for point in open('27B_1_20132.txt'):
    point = list(map(float, point.replace(',', '.').split()))
    clasters.append([point])
    for claster in clasters[:-1]:
        if any(dist(point, claster_point) < 1 for claster_point in claster):
            clasters[-1] += claster
            clasters.remove(claster)


def extreme_point(claster_1, claster_2):
    distances = []
    for point_1 in claster_1:
        for point_2 in claster_2:
            distances.append([dist(point_1, point_2), [point_1, point_2]])
    return min(distances)[1]


extreme_points = [extreme_point(clasters[0], clasters[1]), extreme_point(clasters[0], clasters[2]),
                  extreme_point(clasters[1], clasters[2])]
#print(len(clasters))
print(abs(int(sum(p1[0] + p2[0] for p1, p2 in extreme_points) / (2 * len(extreme_points)) * 10000)), end=' ')
print(abs(int(sum(p1[1] + p2[1] for p1, p2 in extreme_points) / (2 * len(extreme_points)) * 10000)))

Номер