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

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