27_0120

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

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

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

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

Каждое судно характеризуется типом, классом скорости и флагом опасности груза:

Класс скорости — целое число от $1$ до $5$. Флаг — буква H (опасный груз) или L (обычный груз). Значения записаны слитно: буква типа, цифра класса скорости, буква флага (например, T4H). В данных на файл встречается одно судно с классом скорости $0$ — оно стоит на якоре или терпит бедствие, в диапазон классов $1$–$5$ не входит и ни в один из нижеописанных подсчётов не попадает.

В каждой строке файла записаны координата $x$, координата $y$, затем характеристика.

В файле А хранятся данные о судах двух зон, где $H=6{,}5$, $W=5{,}0$. Известно, что количество судов не превышает $1800$.

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

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

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

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

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

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

• 27_0120A.txt
• 27_0120B.txt