Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на N непересекающихся непустых подмножеств (кластеров), таких что точки каждого подмножества лежат внутри прямоугольника со сторонами длиной H и W, причём эти прямоугольники между собой не пересекаются. Стороны прямоугольников не обязательно параллельны координатным осям. Гарантируется, что такое разбиение существует и единственно для заданных размеров прямоугольников.
Назовём центром кластера одну из звёзд на графике, сумма расстояний от которой до всех остальных звёзд кластера минимальна.
Требуется найти в каждом кластере по одной звезде M(x
m, y
m), расстояние от которой до центра максимально возможно. Гарантируется, что в каждом кластере есть только одна единственная возможная точка M.
Расстояние между двумя точками 𝐴(𝑥1 ,𝑦1 ) и 𝐵(𝑥2 ,𝑦2 ) на плоскости вычисляется по формуле:
\(𝑑(𝐴,𝐵) = \sqrt{(𝑥_2 − 𝑥_1 )^2+ (𝑦_2 − 𝑦_1)^2 }\).
В файле А хранятся данные о звёздах
трёх кластеров, где Н=3, W=3 для каждого кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата х, затем координата у. Значения даны в условных единицах. Известно, что количество звёзд не превышает 1000.
В файле Б хранятся данные о звёздах
пяти кластеров, где Н=4, W=4 для каждого кластера. Известно, что количество звёзд не превышает 10 000.
Структура хранения информации о звездах в файле Б аналогична файлу А.
Для каждого файла определите координаты звёзд M(xm, ym) для каждого кластера, затем вычислите два числа: Pх – среднее арифметическое абсцисс всех точек M, и Py – среднее арифметическое ординат всех звёзд M. В ответе запишите четыре числа: в первой строке сначала целую часть произведения |Pх| × 100 000, затем целую часть произведения |Py| × 100 000 для файла А, во второй строке – аналогичные данные для файла Б. Возможные данные одного из файлов иллюстрированы графиком.
Внимание! График приведён в иллюстративных целях для произвольных значений, не имеющий отношения к заданию. Для выполнения задания используйте данные из прилагаемых файлов.