Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат.
Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на непересекающихся непустых подмножеств (кластеров), таких что точки каждого подмножества лежат внутри прямоугольника со сторонами длиной H и W, причём эти прямоугольники между собой не пересекаются.
Стороны прямоугольников не обязательно параллельны координатным осям.
Гарантируется, что такое разбиение существует и единственно.
Для каждой звезды дана характеристика: тип цвета, тип светимости и её размер в соответствии с таблицей.
Решение 1. Кластеризация по диагонали и жёлтый карлик
Шаг 1. Что нужно найти
# Задание 27: кластеры, медоид, жёлтый карлик
В файле два наклонных кластера. Нужны координаты ближайшего к центру жёлтого карлика в самом большом кластере: Ax и Ay, затем целые части произведений на 10 000.
Шаг 2. Подключаем hypot
from math import hypot
Функция hypot(dx, dy) считает длину гипотенузы — евклидово расстояние между двумя точками на плоскости. Ею удобно пользоваться вместо корня из суммы квадратов.
Шаг 3. Читаем файл со звёздами
stars = []
for s in open("task27_file_277767.csv"):
parts = s.replace(",", ".").replace("\t", " ").split()
if len(parts) < 3:
continue
stars.append({"x": float(parts[0]), "y": float(parts[1]), "spec": parts[2]})
В песочнице файл называется task27_file_277767.csv. В каждой строке: координата x, координата y и характеристика звезды. Запятую в числах меняем на точку, табуляцию — на пробел.
Шаг 4. Что такое жёлтый карлик
def is_yellow_dwarf(spec):
# жёлтый — Z (в данных встречается и G…V); карлик — класс светимости V
return (spec.startswith("G") or spec.startswith("Z")) and spec.endswith("V")
По таблице варианта жёлтый цвет — Z, карлик — класс светимости V. В данных встречаются также обозначения на G…V, поэтому проверка допускает оба варианта цвета.
Шаг 5. Центр кластера — медоид
def medioid(cluster):
best = cluster[0]
best_sum = 10 ** 18
for p in cluster:
total = sum(hypot(p["x"] - q["x"], p["y"] - q["y"]) for q in cluster)
if total < best_sum:
best_sum = total
best = p
return best
По условию центр — звезда кластера, сумма расстояний от которой до всех остальных звёзд этого кластера минимальна. Такую точку называют медоидом.
Шаг 6. Почему делим по диагонали
clusters = [
[s for s in stars if s["y"] > s["x"] + 3],
[s for s in stars if s["y"] <= s["x"] + 3],
]
Прямоугольники кластеров наклонены к осям. На плоскости видно две полосы, разделённые прямой примерно y = x + 3. Точки выше линии — один кластер, ниже или на линии — второй.
Шаг 7. Кластер с наибольшим числом звёзд
big = max(clusters, key=len)
В условии нужны Ax и Ay для кластера с наибольшим количеством звёзд. Берём его через max(..., key=len).
Шаг 8. Центр большого кластера
center = medioid(big)
Считаем медоид выбранного кластера — это «центроид» по условию задачи.
Шаг 9. Жёлтые карлики большого кластера
yellows = [s for s in big if is_yellow_dwarf(s["spec"])]
Оставляем только те звёзды большого кластера, которые проходят проверку is_yellow_dwarf.
Шаг 10. Ближайший жёлтый карлик
nearest = min(
yellows,
key=lambda s: hypot(s["x"] - center["x"], s["y"] - center["y"]),
)
Ax, Ay = nearest["x"], nearest["y"]
Среди жёлтых карликов выбираем звезду с минимальным расстоянием до центра. Её координаты и есть Ax и Ay.
Шаг 11. Формат ответа
print(int(Ax * 10000), int(Ay * 10000))
В ответе — целые части произведений координат на 10 000. Ожидается: 40410 62433.
