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