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

(Ю. Дрождинин) Учёный решил провести кластеризацию некоторого множества звёзд по их расположению на карте звёздного неба. Кластер звёзд – это набор звёзд (точек) на графике. Каждый кластер имеет форму эллипса, причём эти эллипсы между собой не пересекаются. Мостом назовем минимальное расстояние между кластерами. Мост образует пара звёзд из разных кластеров. Эти звезды назовем маяками. В группе из N кластеров каждый кластер имеет N–1 маяков. Расстояние между двумя точками A(x₁, y₁) и B(x₂, y₂) вычисляется по формуле:

Даны два входных файла (файл A и файл Б). В файле А хранятся данные о звёздах 2-х кластеров, в файле Б хранятся данные о звёздах 3-х кластеров. Для файла А найдите маяк в каждом кластере, а затем определите два числа: P_x – сумму абсцисс маяков, и P_y – сумму ординат маяков. Для файла Б найдите два числа: M_min – длину наименьшего моста между кластерами и M_max – максимальную длину среди всех мостов.
В ответе запишите четыре числа: в первой строке сначала целую часть абсолютного значения произведения P_x×100000, затем целую часть абсолютного значения произведения P_y×100000, во второй строке сначала целую часть произведения M_min×100000, затем целую часть произведения M_max×100000.