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

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