Кластеризация звёздных точек
Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Необходимо разбить множество точек на непересекающиеся непустые кластеры так, чтобы точки каждого кластера лежали внутри прямоугольника со сторонами длиной $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=6$. В файле Б находятся координаты точек трёх кластеров, для каждого из которых $H=8$ и $W=8$. В каждой строке файла записаны координаты одной точки: сначала абсцисса, затем ордината. Для каждого файла определите координаты центров кластеров, затем вычислите $P_x$ — среднее арифметическое абсцисс центров, и $P_y$ — среднее арифметическое ординат центров. Для каждого файла найдите абсолютные значения целых частей произведений $P_x\times10000$ и $P_y\times10000$.
Условие как в банке ФИПИ — открыть и сверить
| |||||||
| |
Формат: число или слово без единиц измерения; дробную часть отделяйте запятой.
1Мягкая — с чего смотретьуровень 1 из 3
Сначала разделите точки на кластеры по условию о непересекающихся прямоугольниках.
2Наводящая — какие числа считатьуровень 2 из 3
Для каждой точки кластера вычислите сумму евклидовых расстояний до всех остальных точек этого кластера и выберите точку с минимальной суммой.
3Прямая — фактически решениеуровень 3 из 3
После нахождения центров вычислите $P_x$ и $P_y$ отдельно для каждого файла, затем возьмите $\left\lfloor |P_x\times10000|\right\rfloor$ и $\left\lfloor |P_y\times10000|\right\rfloor$.