27_0122

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

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

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

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

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

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

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

В ответе запишите четыре числа: в первой строке — сначала целую часть произведения $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_0122A.txt
• 27_0122B.txt