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

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