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

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