27_0172

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

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

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

Будем называть центром фронта станцию этого фронта с баллом облачности не менее V, сумма расстояний от которой до всех остальных станций этого же фронта с баллом облачности не менее V минимальна. Для каждого фронта гарантируется единственность такого центра. Расстояние между двумя точками $A(x_1, y_1)$ и $B(x_2, y_2)$: $\textit{d}(A, B) = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}$

В файле A хранятся данные о станциях двух фронтов, где H=6,5, W=4,5. В каждой строке: координата x, координата y, характеристика. Количество станций не превышает 1000.

В файле Б — данные о станциях трёх фронтов, где H=6,5, W=5. Количество станций не превышает 10 000. Структура аналогична файлу А.

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

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

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

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

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

• 27_0172A.txt
• 27_0172B.txt