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

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

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