Задание 27 ЕГЭ, информатика: Кластеризация

Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на N непересекающихся непустых подмножеств (кластеров), таких, что точки каждого подмножества лежат внутри прямоугольника со сторонами длиной H и W, причём эти прямоугольники между собой не пересекаются. Стороны прямоугольников не обязательно параллельны координатным осям.

Гарантируется, что такое разбиение существует и единственно для заданных размеров прямоугольников.

Будем называть межкластерным диаметром двух кластеров максимальное расстояние между двумя точками, одна из которых принадлежит одному кластеру, а вторая  — другому. Для каждой пары кластеров гарантируется, что межкластерный диаметр образует единственная пара точек. Расстояние между двумя точками на плоскости A(x₁, y₁) и B(x₂, y₂) вычисляется по формуле:

В файле A хранятся данные о звёздах двух кластеров, где H  =  6, W  =  5 для каждого кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата x, затем координата y. Значения даны в условных единицах. Известно, что количество звёзд не превышает 1000.

В файле Б хранятся данные о звёздах трёх кластеров, где H  =  6, W  =  5 для каждого кластера. Известно, что количество звёзд не превышает 10 000.

Структура хранения информации о звёздах в файле Б аналогична структуре в файле A.

Известно, что в файле Б имеются координаты ровно четырёх «лишних» точек, являющихся аномалиями, возникшими в результате помех при передаче данных. Эти четыре точки не относятся ни к одному из кластеров, их учитывать не нужно.

Для обоих файлов определите межкластерные диаметры для каждой пары различных кластеров. Для файла А найдите два числа: P_x  — модуль разности абсцисс точек, образующих межкластерный диаметр и P_y – сумму ординат точек, образующих межкластерный диаметр. Для файла Б найдите два числа: Q₁  — сумму всех межкластерных диаметров и Q₂  — максимальное расстояние от какой-либо точки, образующей межкластерный диаметр, до точки с координатами (1, 1).

В ответе запишите четыре числа: в первой строке – сначала целую часть произведения P_x × 1000, затем целую часть абсолютного значения произведения P_y × 1000; во второй строке – сначала целую часть произведения Q₁ × 100, затем целую часть произведения Q₂ × 100. Возможные данные одного из файлов иллюстрированы графиком.

Внимание! График приведён в иллюстративных целях для произвольных значений, не имеющих отношения к заданию.

Для выполнения задания используйте данные из прилагаемого файла.

Ответ: