Задание 27

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

Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на N непересекающихся непустых подмножеств (кластеров), таких что точки каждого подмножества лежат внутри прямоугольника со сторонами длиной H и W, причём эти прямоугольники между собой не пересекаются. Стороны прямоугольников не обязательно параллельны координатным осям. Гарантируется, что такое разбиение существует и единственно для заданных размеров прямоугольников. Изолированной точкой назовём точку, в единичном окрестности от которой находится наименьшее количество точек кластера. Если таких точек несколько, то выбирается точка с наибольшей координатой y. Расстояние между двумя точками на плоскости A(x₁, y₁) и B(x₂, y₂) вычисляется по формуле: d(A, B) = √((x₂ - x₁)² + (y₂ - y₁)²). В файле A хранятся данные о звёздах четырёх кластеров, где H=3, W=3 для каждого кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата x, затем координата y. Значения даны в условных единицах. Известно, что количество звёзд не превышает 1000. В файле B хранятся данные о звёздах семи кластеров, где H=5, W=5 для каждого кластера. Известно, что количество звёзд не превышает 10 000. Структура хранения информации о звездах в файле B аналогична файлу А. Для каждого файла определите координаты изолированной точки каждого кластера, затем вычислите два числа: Pₓ – среднее арифметическое абсцисс изолированных точек кластеров, и P_y –среднее арифметическое ординат изолированных точек кластеров. В ответе запишите четыре числа: в первой строке сначала целую часть произведения |Pₓ| × 100 000, затем целую часть произведения |P_y| × 100 000 для файла А, во второй строке – аналогичные данные для файла Б. Внимание! График приведён в иллюстративных целях для произвольных значений, не имеющих отношения к заданию. Для выполнения задания используйте данные из прилагаемого файла.

На сайте запишите все числа ответа в одну строку через пробел — по строкам таблицы ответа слева направо.