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

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