27_0182

На карте морской акватории отмечены координаты судов системы автоматической идентификации. Требуется провести кластеризацию точек — разбить их множество на $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 не входит и ни в один из нижеописанных подсчётов не попадает.

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

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

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

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

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

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

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

• 27_0182A.txt
• 27_0182B.txt