27_0184

На карте города отмечены координаты стационарных датчиков контроля воздуха. Требуется провести кластеризацию точек — разбить их множество на $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. Смена — буква D (дневная) или N (ночная). Значения записаны слитно: буква загрязнителя, цифра уровня, буква смены (например, S5D).

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

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

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

Для файла Б определите координаты центра каждой зоны, затем найдите два числа: $B_1$ — расстояние между центрами зон с наименьшим и наибольшим количеством датчиков CO₂ дневной смены (C, любой уровень, D), и $B_2$ — среднее арифметическое расстояний от центра наименьшей по количеству датчиков зоны до датчиков пыли уровня 2 (P2, любая смена) этой зоны.

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

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

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

• 27_0184A.txt
• 27_0184B.txt