Решение: Кластеризация точек звёзд
Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Требуется разбить множество точек на непересекающиеся непустые кластеры так, чтобы точки каждого кластера лежали внутри прямоугольника со сторонами длиной $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$ и $W=4{,}5$ для каждого кластера. В файле Б хранятся координаты точек трёх кластеров, где $H=6$ и $W=5$ для каждого кластера. В файле Б имеются ровно три лишние точки-аномалии, которые не относятся ни к одному кластеру.
Для файла А найдите суммы абсцисс и ординат центров кластеров: $P_x$ и $P_y$. Для файла Б найдите минимальное и максимальное расстояния между центрами различных кластеров: $Q_1$ и $Q_2$.
Решение по шагам
5 шаговСначала необходимо прочитать координаты точек из файлов А и Б и разделить точки на кластеры по условию о прямоугольниках заданных размеров.
Для каждого кластера следует найти точку, для которой сумма евклидовых расстояний до всех остальных точек кластера минимальна. Эта точка является центром кластера.
Для файла А вычисляются суммы координат центров: $P_x=\sum x_i$ и $P_y=\sum y_i$.
Для файла Б три аномальные точки исключаются, после чего вычисляются все попарные расстояния между тремя центрами. Минимальное из них равно $Q_1$, максимальное — $Q_2$.
Числа в ответе получают как абсолютные значения целых частей произведений $P_x\times10000$, $P_y\times10000$, $Q_1\times10000$ и $Q_2\times10000$.
Числовой ответ невозможно определить без содержимого файлов А и Б: во вложении представлен только скриншот условия.
Этот ответ получен в разборе, но не сверен с официальным ключом из банка — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Учитывают три аномальные точки файла Б при поиске центров.
Используют среднее арифметическое координат вместо точки с минимальной суммой расстояний.
Сравнивают расстояния между всеми точками вместо расстояний между центрами кластеров.
Забывают взять абсолютную величину целой части произведения на 10000.