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

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