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

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