Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на N непересекающихся непустых подмножеств (кластеров), таких что точки каждого подмножества лежат внутри прямоугольника со сторонами длиной H и W, причём эти прямоугольники между собой не пересекаются. Стороны прямоугольников не обязательно параллельны координатным осям.
Гарантируется, что такое разбиение существует и единственно для заданных размеров прямоугольников.
Будем называть центром кластера точку в нём, сумма расстояний от которой до всех остальных точек кластера минимальна. У каждого кластера есть гарантированно единственный центр. Расстояние между двумя точками на плоскости A(x1,y1) и B(x2,y2) вычисляется по формуле:.PNG)
В файле A хранятся данные о звёздах двух кластеров, где H=6,W=4,5 для каждого кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата xx, затем координата yy. Значения даны в условных единицах. Известно, что количество звёзд не превышает 1000.
В файле Б хранятся данные о звёздах трёх кластеров, где H=6,W=5для каждого кластера. Известно, что количество звёзд не превышает 1000. Структура хранения информации о звездах в файле Б аналогична файлу А.
Известно, что в файле Б имеются координаты ровно трёх «лишних» точек, являющихся аномалиями, возникшими в результате помех при передаче данных. Эти три точки не относятся ни к одному из кластеров, их учитывать не нужно.
Для файла А определите координаты центра каждого кластера, затем найдите два числа: Px — сумму абсцисс центров кластеров, и Py — сумму ординат центров кластеров. Для файла Б найдите два числа: Q1 — среднее арифметическое расстояний от центров кластеров до ближайших к ним точек своих кластеров (по одной точке на кластер), и Q2 — сумму расстояний от каждого центра кластера до самой дальней точки этого же кластера.
В ответе запишите четыре числа: в первой строке — сначала абсолютную величину целой части произведения Px×10 000, затем абсолютную величину целой части произведения Py×10 000; во второй строке — сначала целую часть произведения Q1×10 000, затем целую часть произведения Q2×10 000.
Файл