27_0123

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

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

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

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

Будем называть центром группы точку этой группы, сумма расстояний от которой до всех остальных точек группы минимальна (центр единствен). Расстояние:

$$d(A, B) = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}.$$

В файле А — гонщики двух групп, $H=6{,}5$, $W=4{,}5$, не более $1000$. В каждой строке: координата $x$, координата $y$, характеристика. В файле Б — три группы, $H=6{,}5$, $W=5$, не более $10\thinspace 000$; структура аналогична.

Для файла А найдите: $A_1$ — расстояние от центра группы с бóльшим количеством гонщиков до финиша $(0{,}0)$, и $A_2$ — в группе с наибольшим количеством горняков-разделочников минимальное расстояние от центра этой группы до горняка-разделочника (отличного от самого центра).

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

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

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

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

• 27_0123A.txt
• 27_0123B.txt