На плоскости с декартовой системой координат изображен фрагмент базы данных «Сотрудники». Для каждого сотрудника известен возраст и стаж работы. Предприятие решило провести кластеризацию полученных точек на графике (по оси абсцисс – возраст сотрудника, по оси ординат – стаж работы в у. е.), то есть разбить их множество на N непересекающихся непустых подмножеств (кластеров), таких что точки каждого подмножества лежат внутри прямоугольника со сторонами длиной H и W, причём эти прямоугольники между собой не пересекаются. Стороны прямоугольников не обязательно параллельны координатным осям. Гарантируется, что любые два сотрудника с одинаковыми возрастами имеют разный стаж работы.
Гарантируется, что такое разбиение существует и единственно для заданных размеров прямоугольников.
Назовём самой нижней точкой кластера точку с наименьшим значением ординаты.
Необходимо определить такую точку в каждом кластере, расстояние до которой от самой нижней точки минимально возможно, при этом искомая точка не является самой нижней. Расстояние между двумя точками на плоскости �(�!, �!) и �(�", �") вычисляется по формуле:
�(�,�) = +(�" − �!)" + (�" − �!)" .
В файле А хранятся данные о звёздах двух кластеров, где Н=17, W=17 для каждого кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата х, затем координата у. Значения даны в условных единицах. Известно, что количество звёзд не превышает 1000. В файле Б хранятся данные о звёздах трёх кластеров, где Н=17, W=17 для каждого кластера. Известно, что количество звёзд не превышает 10 000.
Структура хранения информации о звездах в файле Б аналогична файлу А.
Для каждого файла определите координаты самой нижней точки для каждого кластера, затем вычислите два числа: Sx – среднее арифметическое абсцисс найденных точек, и Sy – среднее арифметическое ординат найденных точек. В ответе запишите четыре числа: в первой строке сначала целую часть произведения |Sx| × 10 000, затем целую часть произведения |Sy| × 10 000 для файла А, во второй строке – аналогичные данные для файла Б.
Возможные данные одного из файлов иллюстрированы графиком.
Внимание! График приведён в иллюстративных целях для произвольных значений, не имеющий отношения к заданию. Для выполнения задания используйте данные из прилагаемых файлов.
