27_0121

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

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

Будем называть центром кластера точку этого кластера, сумма расстояний от которой до всех остальных точек кластера минимальна. Для каждого кластера гарантируется единственность его центра. Расстояние между двумя точками на плоскости $A(x_1, y_1)$ и $B(x_2, y_2)$ вычисляется по формуле:

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

Расстояние от точки до начала координат $O(0; 0)$ вычисляется по той же формуле.

В файле А хранятся координаты точек двух кластеров, где $H=8{,}5$ и $W=2$ для каждого кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата $x$, затем координата $y$. Значения даны в условных единицах. Известно, что количество звёзд не превышает $1000$. Известно, что в файле А имеются координаты ровно двух «лишних» точек, являющихся аномалиями, возникшими в результате помех при передаче данных. Эти точки не относятся ни к одному из кластеров, их учитывать не нужно.

В файле Б хранятся координаты точек трёх кластеров, где $H=7$ и $W=1{,}5$ для каждого кластера. Известно, что количество звёзд не превышает $10\thinspace 000$. Структура хранения информации в файле Б аналогична структуре в файле А. Известно, что в файле Б имеются координаты ровно трёх «лишних» точек-аномалий, которые также учитывать не нужно.

Для файла А найдите два числа: $P_1$ — расстояние от начала координат до самого удалённого от него центра кластера и $P_2$ — количество точек в этом кластере.

Для файла Б найдите два числа: $Q_1$ — расстояние от начала координат до ближайшего к нему центра кластера и $Q_2$ — максимальное расстояние от этого (ближайшего) центра до точки его кластера.

В ответе запишите четыре числа: в первой строке — сначала целую часть произведения $P_1 \cdot 10\thinspace 000$, затем число $P_2$; во второй строке — сначала целую часть произведения $Q_1 \cdot 10\thinspace 000$, затем целую часть произведения $Q_2 \cdot 10\thinspace 000$.

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

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

• 27_0121A.txt
• 27_0121B.txt