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