27_0128

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

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

Для каждой посылки задана характеристика: тип груза, весовой класс и приоритет в соответствии с таблицей.

Весовой класс обозначается арабской цифрой от $1$ до $5$. Значения записаны в характеристике слитно: обозначение типа груза, весовой класс, обозначение приоритета (например, F5H).

Будем называть центром зоны точку этой зоны, сумма расстояний от которой до всех остальных точек зоны минимальна. Для каждой зоны гарантируется единственность её центра. Расстояние между двумя точками на плоскости $A(x_1, y_1)$ и $B(x_2, y_2)$ вычисляется по формуле:

$$d(A, B) = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}.$$

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

В файле Б хранятся данные о посылках трёх зон, где $H = 6{,}5$, $W = 5$ для каждой зоны. Известно, что количество посылок не превышает $10\thinspace 000$. Структура хранения информации аналогична файлу А.

Для файла А определите координаты центра каждой зоны, затем найдите два числа: $A_1$ — минимальное расстояние между двумя различными хрупкими посылками весового класса $5$, находящимися в одной зоне, и $A_2$ — максимальное расстояние от центра зоны с наибольшим количеством посылок до опасной срочной посылки этой же зоны.

Для файла Б определите координаты центра каждой зоны, затем найдите два числа: $B_1$ — расстояние между центрами зон с наименьшим и наибольшим количеством обычных посылок весового класса $3$, и $B_2$ — среднее арифметическое расстояний от центра зоны с наименьшим количеством посылок до опасных посылок весового класса $2$ этой же зоны.

В ответе запишите четыре числа: в первой строке – сначала целую часть произведения $A_1$ × $10\thinspace 000$, затем целую часть произведения $A_2$ × $10\thinspace 000$; во второй строке – сначала целую часть абсолютного значения произведения $B_1$ × $10\thinspace 000$, затем целую часть абсолютного значения произведения $B_2$ × $10\thinspace 000$.

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

Файлы к заданию:

• 27_0128A.txt
• 27_0128B.txt