Задание №27: Кластерный анализ и геометрические алгоритмы

(В. Ланская, Р. Ягафаров) Шёл 2077 год. Ученому необходимо провести кластеризацию населенных пунктов двух больших районов на картах планет Информатикус и Алгоритмикус. Район (кластер) – это группа населенных пунктов, которые находятся внутри прямоугольника высотой H и шириной W. Каждый населенный пункт обязательно принадлежит только одному району. Столица района (или центроид) – это такой населенный пункт, сумма манхэттенских расстояний от которого до всех других населённых пунктов в кластере минимальна. Манхэттенское расстояние между двумя точками A(x₁, y₁) и B(x₂, y₂) вычисляется по формуле:
Даны два входных файла (файл A и файл Б). В файле A хранятся данные о точках двух кластеров. В каждой строке записана информация о расположении одной точки: сначала координата x, затем координата y (в условных единицах). Известно, что количество точек не превышает 1000. В файле Б той же структуры хранятся данные о точках трёх кластеров. Известно, что количество точек не превышает 10 000. Возможные данные одного из файлов иллюстрированы графиком.
Для каждого файла определите координаты центра каждого кластера, затем вычислите два числа: Px – среднее арифметическое абсцисс центров кластеров, и Py – среднее арифметическое ординат центров кластеров. В ответе запишите четыре числа: в первой строке сначала целую часть абсолютного значения произведения Px×10 000, затем целую часть абсолютного значения произведения Py×10 000 для файла А, во второй строке – аналогичные данные для файла Б.