Олимпиадный тренинг

Задача . в07-27


Задача

Темы:
Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на N непересекающихся непустых подмножеств (кластеров), таких что точки каждого подмножества лежат внутри прямоугольника со сторонами длиной H и W, причём эти прямоугольники между собой не пересекаются. Стороны прямоугольников не обязательно параллельны координатным осям.
Гарантируется, что такое разбиение существует и единственно для заданных размеров прямоугольников.
В файле А хранятся данные о звёздах двух кластеров, где Н=2, W=3 для каждого кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата х, затем координата у. Значения даны в условных единицах. Известно, что количество звёзд не превышает 1000.
В файле Б хранятся данные о звёздах трёх кластеров, где Н=3, W=4 для каждого кластера.
Известно, что количество звёзд не превышает 10 000.
Структура хранения информации о звездах в файле Б аналогична файлу А. Для каждого файла определите по одной звезде M(x, y) у каждого кластера так, чтобы сумма квадратов расстояний между ними была максимально возможной, а затем вычислите два числа: Pх – среднее арифметическое абсцисс найденных звёзд M, и Py – среднее арифметическое ординат найденных звёзд M.
Расстояние между двумя точками \(𝐴(𝑥_1, 𝑦_1)\) и \(𝐵(𝑥_2,𝑦_2) \)на плоскости вычисляется по формуле: \(𝑑(𝐴,𝐵)=\sqrt{(𝑥_2−𝑥_1)^2+(𝑦_2-𝑦_1)^2}\) .
В ответе запишите четыре числа: в первой строке сначала целую часть произведения |Pх| × 10 000, затем целую часть произведения |Py| × 10 000 для файла А, во второй строке – аналогичные данные для файла Б.

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


Внимание! График приведён в иллюстративных целях для произвольных значений, не имеющий отношения к заданию. Для выполнения задания используйте данные из прилагаемых файлов.

time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
Комментарий учителя