27_0110

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

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

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

Балл облачности обозначается римской цифрой от I до VIII. Значения записаны слитно: обозначение осадков, балл облачности, обозначение ветра (например, RVIIIN).

Будем называть центром фронта станцию этого фронта с баллом облачности не менее V, сумма расстояний от которой до всех остальных станций этого же фронта с баллом облачности не менее V минимальна. Для каждого фронта гарантируется единственность такого центра. Расстояние между двумя точками $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$ — расстояние от центра фронта с бóльшим количеством станций до самой удалённой дождевой станции этого фронта, и $A_2$ — расстояние от центра фронта с меньшим количеством станций до ближайшей (отличной от самого центра) снежной станции этого фронта.

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

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

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

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

• 27_0110A.txt
• 27_0110B.txt