Задание №27: Кластерный анализ и геометрические алгоритмы

(А. Сражаев) Учёный решил провести кластеризацию некоторого множества звёзд по их расположению на карте звёздного неба. Кластер звёзд – это набор звёзд (точек) на графике. Каждая звезда обязательно принадлежит только одному из кластеров; ближайшие точки разных кластеров отстоят друг от друга не менее, чем на единичное расстояние. Центр кластера – это одна из звёзд на графике, сумма расстояний от которой до всех остальных звёзд кластера минимальна. Расстояние между двумя точками A(x₁, y₁) и B(x₂, y₂) вычисляется по формуле:
Даны два входных файла (файл A и файл Б). В файле A хранятся данные о звёздах двух кластеров. В каждой строке записана информация о расположении на карте одной звезды: сначала координата x, затем координата y (в условных единицах). Известно, что количество звёзд не превышает 1000. В файле Б аналогичной структуры хранятся данные о звёздах пяти кластеров. Известно, что количество звёзд не превышает 10 000. Возможные данные одного из файлов иллюстрированы графиком.
Для файла А определите координаты центра каждого кластера, затем найдите два числа: R₁ – наименьшее расстояние между различными точками кластера с наибольшим количеством точек, и R₂ – наибольшее расстояние между различными точками кластера с наименьшим количеством точек. Для файла Б определите координаты точки M (центра системы кластеров) как среднее арифметическое соответствующих координат центров всех найденных кластеров. Затем найдите значения Q₁ – количество точек в кластере, центр которого находится на наименьшем расстоянии от точки M, и Q₂ – количество точек в кластере, центр которого находится на наибольшем расстоянии от точки M. Гарантируется, что во всех кластерах количество точек различно. В ответе запишите четыре числа: в первой строке – сначала целую часть произведения R₁ × 100 000, затем целую часть произведения R₂ × 100000; во второй строке – сначала число Q₁, затем число Q₂.