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

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