Задание выполняется с использованием прилагаемых файлов.
Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, то есть разбить их множество на N непересекающихся непустых подмножеств (кластеров), таких что точки каждого подмножества лежат внутри прямоугольника со сторонами H и W, причём эти прямоугольники между собой не пересекаются. Стороны прямоугольников не обязательно параллельны координатным осям.
Гарантируется, что такое разбиение существует и единственно. Во всех кластерах количество точек различно.
Для каждой звезды задана характеристика – набор символов, включающий спектральный класс (обозначается латинской буквой), подкласс светимости (обозначается арабской цифрой) и класс светимости (обозначается римской цифрой).
Спектральный класс звезды определяется в соответствии с таблицей:
| Спектральный класс звёзд |
| O |
B |
A |
F |
G |
K |
M |
| Голубая |
Бело-голубая |
Белая |
Жёлто-белая |
Жёлтая |
Оранжевая |
Красная |
Класс светимости звезды определяется в соответствии с таблицей:
| Класс светимости звезды |
| I |
II |
III |
IV |
V |
VI |
VII |
| Сверхгиганты |
Яркие гиганты |
Гиганты |
Субгиганты |
Карлики |
Субкарлики |
Белые карли |
Будем называть центром кластера точку этого кластера, сумма расстояний от которой до всех остальных точек кластера минимальна. Для каждого кластера гарантируется единственность его центра. Расстояние между двумя точками на плоскости А (х1, y1) и B (х2, y2) вычисляется по формуле:
\(d(A, B) = \sqrt{(x_2-x_1)^2+(y_2-y_1)^2}\)
В файле А хранятся данные о звёздах двух кластеров, где Н = 5 и W = 4 для каждого кластера. В каждой строке записана информация одной звезды: координата х, координата у и её характеристика. Значения даны в условных единицах. Известно, что количество точек не превышает 1000.
В файле Б хранятся данные о звёздах трёх кластеров, где Н = 3 и W = 5 для каждого кластера. Известно, что количество точек не превышает 10 000.
Структура хранения информации о звёздах в файле Б аналогична структуре в файле А.
Для файла А определите координаты центра каждого кластера, затем найдите два числа: A1 – абсциссу ближайшего белого гиганта к центру кластера с наименьшим количеством точек, и A2 – ординату ближайшего белого гиганта к центру кластера с наименьшим количеством точек.
Для файла Б определите координаты центра каждого кластера, затем найдите два числа: B1 – расстояние между центрами кластеров с наибольшим и наименьшим количеством красных сверхгигантов, и B2 – максимальное расстояние между двумя жёлтыми карликами, находящимися в одном кластере.
В ответе запишите четыре числа: в первой строке – сначала целую часть произведения A1 × 10 000, затем целую часть произведения A2 × 10 000; во второй строке – сначала целую часть произведения B1 × 10 000, затем целую часть произведения B2 × 10 000.