27_0116

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

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

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

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

Диаметром множества находок будем называть максимальное расстояние между двумя его находками.

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

$$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$ — диаметр множества бронзовых находок в слое с наибольшим количеством находок, и $A_2$ — диаметр множества керамических находок эпохи не ранее V в слое с наименьшим количеством находок.

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

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

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

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

• 27_0116A.txt
• 27_0116B.txt