На плоскости с декартовой системой координат изображен фрагмент базы данных «Сотрудники». Для каждого сотрудника известен возраст и стаж работы. Предприятие решило провести кластеризацию полученных точек на графике (по оси абсцисс – возраст сотрудника, по оси ординат – стаж работы в у. е.), то есть разбить их множество на N непересекающихся непустых подмножеств (кластеров), таких что точки каждого подмножества лежат внутри прямоугольника со сторонами длиной H и W, причём эти прямоугольники между собой не пересекаются. Стороны прямоугольников не обязательно параллельны координатным осям. Гарантируется, что любые два сотрудника с одинаковыми возрастами имеют разный стаж работы. Гарантируется, что такое разбиение существует и единственно для заданных размеров прямоугольников.
Назовём самой верхней точкой кластера точку с наибольшим значением ординаты. Необходимо определить такую точку в каждом кластере, расстояние до которой от самой верхней точки минимально возможно, при этом искомая точка не является самой верхней. Расстояние между двумя точками на плоскости 𝐴(𝑥1,𝑦1) и 𝐵(𝑥2,𝑦2) вычисляется по формуле:
\(d(A, B) = \sqrt{(x_2-x_1)^2 + (y_2-y_1)^2}\)
В файле А хранятся данные о сотрудниках двух кластеров, где Н=3, W=3 для каждого кластера. В каждой строке записана информация о возрасте и стаже работы сотрудника: сначала координата х, затем координата у. Значения даны в условных единицах. Известно, что количество сотрудников не превышает 1000.
В файле Б хранятся данные о сотрудниках трёх кластеров, где Н=3, W=3 для каждого кластера. Известно, что количество сотрудников не превышает 10 000. Структура хранения информации о сотрудниках в файле Б аналогична файлу А.
Для каждого файла определите координаты самой верхней точки для каждого кластера, затем вычислите два числа: Sx – сумма абсцисс найденных точек, и Sy – сумма ординат найденных точек.
В ответе запишите четыре числа: в первой строке сначала целую часть произведения |Sx| × 10 000, затем целую часть произведения |Sy| × 10 000 для файла А, во второй строке – аналогичные данные для файла Б.
Возможные данные одного из файлов иллюстрированы графиком.
Внимание! График приведён в иллюстративных целях для произвольных значений, не имеющий отношения к заданию. Для выполнения задания используйте данные из прилагаемых файлов.
