Задача #3851

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

Уровень ЕГЭ

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

Для каждой звезды дана характеристика: тип цвета, тип светимости и её размер в соответствии с искомой таблицей.

Обозначение	Цвет	Обозначение	Размер
G	белый	I	сверхгигант
J	зелёный	II	яркий гигант
L	синий	III	гигант
N	оранжевый	IV	субгигант
Y	красный	V	карлик
S	голубой	VI	субкарлик
Z	жёлтый	VII	белый карлик

Полученные значения записаны в характеристике слитно: обозначение цвета, светимость (обозначается арабской цифрой) и обозначение размера планеты.

Будем называть центром кластера точку этого кластера, сумма расстояний от которой до всех остальных точек кластера минимальна. Для каждого кластера гарантируется единственность его центра. Расстояние между двумя точками на плоскости $A (x_{1}, y_{1})$ и $B (x_{2}, y_{2})$ вычисляется по формуле: $d (A, B) = \sqrt{(x_{2} - x_{1})^{2} + (y_{2} - y_{1})^{2}}$

В файле A хранятся данные о звёздах двух кластеров, где H=6,5, W=4,5 для каждого кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата x, затем координата y, а затем характеристика звезды. Значения даны в условных единицах. Известно, что количество звёзд не превышает 1000.

В файле B хранятся данные о звёздах трёх кластеров, где H=6,5, W=5 для каждого кластера. Известно, что количество звёзд не превышает 10 000. Структура хранения информации о звездах в файле B аналогична файлу А.

Для файла А определите координаты центра каждого кластера, затем найдите два числа: A₁ – минимальное расстояние от центра
кластера с наибольшим количеством точек до жёлтого яркого гиганта, и A₂ – максимальное расстояние от центра кластера с наименьшим количеством точек до жёлтого яркого гиганта.

Для файла Б определите координаты центра каждого кластера, затем найдите два числа: B₁ – сумма расстояний между двумя различными синими карликами, расположенными в кластере с максимальным количеством точек, и B₂ – расстояние между центрами кластеров с минимальным и медианным количеством синих карликов.

В ответе запишите четыре числа: в первой строке – сначала целую часть произведения A₁ × 10 000, затем целую часть произведения A₂ × 10 000; во второй строке – сначала целую часть абсолютного значения произведения B₁ × 10 000, затем целую часть абсолютного значения произведения B₂ × 10 000.

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

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

Вопрос A

Вопрос B

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

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

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

Ответ

Вопрос A

7112

303310

Вопрос B

5471239

458494

def dist(point1, point2):
    x1, y1, *_ = point1
    x2, y2, *_ = point2
    return ((x1 - x2) ** 2 + (y1 - y2) ** 2) ** 0.5


def get_center(cluster):
    center = None
    min_dist = float('inf')
    for point1 in cluster:
        sum_dist = sum(dist(point1, point2) for point2 in cluster)
        if sum_dist < min_dist:
            min_dist = sum_dist
            center = point1
    return center


def get_by_type(points, color, size):
    return [point for point in points
            if point[2][:1] == color and point[2][2:] == size]


points = []
clusters = [[], []]
for s in open('27A_3_28828.txt'):
    x, y, t = s.replace(',', '.').split()
    x, y = float(x), float(y)
    point = (x, y, t)
    points.append(point)
    if y > 10:
        clusters[0].append(point)
    else:
        clusters[1].append(point)
clusters.sort(key=len)
centers = [get_center(cluster) for cluster in clusters]
points_ZII = get_by_type(points, 'Z', 'II')
dists_max_ZII = [dist(centers[1], point) for point in points_ZII]
dists_min_ZII = [dist(centers[0], point) for point in points_ZII]
print(int(min(dists_max_ZII) * 10000), int(max(dists_min_ZII) * 10000))

points = []
clusters = [[], [], []]
for s in open('27B_3_28828.txt'):
    x, y, t = s.replace(',', '.').split()
    x, y = float(x), float(y)
    point = (x, y, t)
    points.append(point)
    if x > 0:
        clusters[0].append(point)
    elif y > 5:
        clusters[1].append(point)
    else:
        clusters[2].append(point)
clusters.sort(key=len)
points_LV = get_by_type(clusters[2], 'L', 'V')
clusters.sort(key=lambda cluster: len(get_by_type(cluster, 'L', 'V')))
centers = [get_center(cluster) for cluster in clusters]
B1 = sum(dist(point1, point2) for point1 in points_LV for point2 in points_LV) / 2
B2 = dist(centers[0], centers[1])
print(int(B1 * 10000), int(B2 * 10000))

Номер