Кластеры звёзд в прямоугольниках

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

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

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