Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на N непересекающихся непустых подмножеств (кластеров), таких что точки каждого подмножества лежат внутри прямоугольника со сторонами длиной H и W, причём эти прямоугольники между собой не пересекаются. Стороны прямоугольников не обязательно параллельны координатным осям.
Гарантируется, что такое разбиение существует и единственно для заданных размеров прямоугольников.
Гарантируется, что во всех кластерах количество точек различно.
Для каждой звезды задана характеристика – набор символов, включающий спектральный класс (обозначается латинской буквой), подкласс светимости (обозначается арабской цифрой) и класс светимости (обозначается римской цифрой).
Спектральный класс звезды определяется в соответствии с таблицей:
| Спектральный класс звезды | O | B | A | F | G | K | M |
|---|
| Голубая | Бело-голубая | Белая | Желто-белая | Желтая | Оранжевая | Красная |
Класс светимости звезды определяется в соответствии с таблицей:
| Класс светимости звезды | I | II | III | IV | V | VI | VII |
|---|
| Сверхгиганты | Яркие гиганты | Гиганты | Субгиганты | Карлики | Субкарлики | Белые карлики |
Будем называть центром кластера точку этого кластера, сумма расстояний от которой до всех остальных точек кластера минимальна. Для каждого кластера гарантируется единственность его центра. Расстояние между двумя точками на плоскости А (х
1, y
1) и B (х
2, y
2) вычисляется по формуле: √((х
2 − х
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.