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