Средние координаты центров кластеров

Фрагмент звёздного неба спроецирован на плоскость. Точки нужно разбить на N непересекающихся кластеров так, что точки каждого кластера лежат внутри прямоугольника со сторонами H и W (стороны не обязательно параллельны осям), прямоугольники не пересекаются. Разбиение существует и единственно. Центр кластера — его точка, сумма расстояний от которой до всех остальных точек кластера минимальна (центр единственен). Файл A: два кластера, H = 3, W = 3, не больше 1000 точек (в строке — x и y). Файл Б: три кластера, H = 3, W = 3, не больше 10 000 точек. Для каждого файла определите координаты центра каждого кластера, затем вычислите Px — среднее арифметическое абсцисс центров и Py — среднее арифметическое ординат центров. В ответе запишите четыре числа: в первой строке — целую часть Px × 10 000 и целую часть Py × 10 000 для файла А, во второй строке — то же для файла Б.

Источник: ФИПИ (Демо 2025)

Скачать файл: demo2025_27_A.txt, demo2025_27_B.txt. В редакторе он уже лежит рядом с кодом, открывай как на экзамене: open('demo2025_27_A.txt').