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

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