Задача
Учёный решил провести кластеризацию некоторого множества звёзд по их расположению на карте звёздного неба.
Кластер звёзд – это набор звёзд (точек) на графике, лежащий внутри прямоугольника высотой H и шириной W.
Каждая звезда обязательно принадлежит только одному из кластеров.
Истинный центр кластера, или центроид, – это одна из звёзд на графике,
сумма расстояний от которой до всех остальных звёзд кластера минимальна.
Под расстоянием понимается расстояние Евклида между двумя точками A(x1,y1) и B(x2,y2) на плоскости,
которое вычисляется по формуле:
\( d(A,B)=\sqrt{(x2 - x1)^2+(y2 - y1)^2}\)
В файле A хранятся данные о звёздах двух кластеров, где H=3, W=3 для каждого кластера.
В каждой строке записана информация о расположении на карте одной звезды: сначала координата x, затем координата y.
Значения даны в условных единицах. Известно, что количество звёзд не превышает 1000.
В файле B хранятся данные о звёздах трёх кластеров, где H=3, W=3 для каждого кластера.
Известно, что количество звёзд не превышает 10 000.
Структура хранения информации о звездах в файле B аналогична файлу А.
Для каждого файла определите координаты центра каждого кластера, затем вычислите два числа:
Px – среднее арифметическое абсцисс центров кластеров,
и Py – среднее арифметическое ординат центров кластеров.
В ответе запишите четыре числа:
в первой строке сначала целую часть произведения Px×10000, затем целую часть произведения Py×10000 для файла А,
во второй строке – аналогичные данные для файла B.
Возможные данные одного из файлов иллюстрированы графиком.
Внимание! График приведён в иллюстративных целях для произвольных значений, не имеющих отношения к заданию.
Для выполнения задания используйте данные из прилагаемого файла