Задание выполняется с использованием прилагаемых файлов.
Фрагмент карты городских объектов спроецирован на плоскость с декартовой системой координат. Исследователь разбивает множество точек на N кластеров: точки каждого кластера лежат внутри прямоугольника со сторонами H и W (стороны не обязательно параллельны осям). Прямоугольники не пересекаются. Разбиение единственно.
Гарантируется, что такое разбиение существует и единственно для заданных размеров прямоугольников.
Будем называть центром кластера точку этого кластера, сумма расстояний от которой до всех остальных точек кластера минимальна. Для каждого кластера гарантируется единственность его центра. Расстояние между двумя точками на плоскости 𝐴(𝑥1,𝑦1) и 𝐵(𝑥2,𝑦2) вычисляется по формуле: \( d = \sqrt{(x_2-x_1)^2+(y_2-y_1)^2} \).
Файл А (2 кластера, H=5, W=7, не более 1000 точек). Найдите центр каждого кластера. Вычислите Px — максимальное из абсцисс центров, Py — максимальное из ординат центров.
Файл Б (3 кластера, H=4, W=5, не более 10000 точек). Найдите центры. Вычислите Qx — сумму абсцисс центров кластеров с минимальным и максимальным числом точек; Qy — сумму ординат тех же центров.
В ответе запишите четыре числа (по две строки):
строка 1: целая часть (Px × 10000) и целая часть (Py × 10000);
строка 2: целая часть (Qx × 10000) и целая часть (Qy × 10000).