27_0083

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

Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на $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}.$$

В файле А хранятся координаты точек двух кластеров, где $H=6,5$ и $W=4,5$ для каждого кластера. В файле Б хранятся координаты точек трёх кластеров, где $H=5$, $W=4,5$ для каждого кластера. В файле А имеются координаты ровно двух, а в файле Б ровно трёх лишних точек, представляющих аномалии; эти точки учитывать не нужно.

Для файла А определите координаты центра каждого кластера, затем найдите два числа: $P_x$ — расстояние по оси абсцисс между центрами кластеров и $P_y$ — расстояние по оси ординат между центрами кластеров.

Для файла Б определите координаты центра каждого кластера, затем найдите два числа: $Q_1$ — среднее арифметическое расстояний от центра кластера с минимальным количеством точек до точек этого кластера и $Q_2$ — среднее арифметическое расстояний от центра кластера с максимальным количеством точек до точек этого кластера. Гарантируется, что во всех кластерах количество точек различно. Нулевое расстояние от центра кластера до самого себя не учитывается.

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

Возможные данные одного из файлов проиллюстрированы графиком.

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

• 27_0083A.txt
• 27_0083B.txt