27_0178

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

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

Эпоха обозначается римской цифрой от I до VII. Значения записаны слитно: обозначение материала, эпоха, обозначение сохранности (например, PIIIH).

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

В файле A — находки двух слоёв, H=6,5, W=4,5, не более 1000. В каждой строке: координата x, координата y, характеристика. В файле Б — три слоя, H=6,5, W=5, не более 10 000; структура аналогична.

Для файла А найдите: $A_1$ – диаметр множества бронзовых находок в слое с наибольшим количеством находок, и $A_2$ – диаметр множества керамических находок эпохи не ранее V в слое с наименьшим количеством находок.

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

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

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

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

• 27_0178A.txt
• 27_0178B.txt