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

Учёный решил провести кластеризацию некоторого множества звёзд по их расположению на карте звёздного неба. Кластер звёзд – это набор звёзд (точек) на графике. Каждая звезда обязательно принадлежит только одному из кластеров. Межкластерный мост – это отрезок наименьшей длины между парой звёзд, одна из которых принадлежит одному кластеру, а другая – второму. Гарантируется, что для каждой пары кластеров межкластерный мост образует только одна пара звёзд. Расстояние между двумя точками A(x₁, y₁) и B(x₂, y₂) вычисляется по формуле:
Даны два входных файла (файл A и файл Б). В файле A хранятся данные о звёздах двух кластеров. В каждой строке записана информация о расположении на карте одной звезды: сначала координата x, затем координата y (в условных единицах). Известно, что количество звёзд не превышает 1000. В файле Б хранятся данные о звёздах трёх кластеров. Известно, что количество звёзд не превышает 10 000. Структура хранения информации о звездах в файле Б аналогична файлу А. В файле Б имеются координаты ровно трёх «лишних» точек, являющихся аномалиями, возникшими в результате помех при передаче данных. Эти три точки не относятся ни к одному из кластеров, их учитывать не нужно.
Для файла А определите координаты точек, образующих межкластерный мост, затем найдите два числа: P_x – среднее арифметическое абсцисс точек, образующих межкластерный мост, и P_y – среднее арифметическое ординат точек, образующих межкластерный мост. Для файла Б найдите два числа: Q₁ – сумму длин всех межкластерных мостов, и Q₂ – наименьшее расстояние от какой-либо точки, образующей межкластерный мост, до точки (20; 15).
В ответе запишите четыре числа: в первой строке – сначала целую часть произведения P_x×10 000, затем целую часть произведения P_y×10 000; во второй строке – сначала целую часть произведения Q₁×10 000, затем целую часть произведения Q₂×10 000.