Задача #3297

(Д. Бахтиев) Учёный наблюдает проекцию звёздного скопления на плоскость с декартовой системой координат. Полученные точки (звёзды) необходимо разбить на N непересекающихся непустых кластеров. Каждый кластер размещается внутри прямоугольника размером H x W, при этом прямоугольники не перекрываются. Стороны прямоугольников не обязаны быть параллельны осям координат. Гарантируется, что такое разбиение единственно для заданных размеров прямоугольников. Расстояние между двумя точками $A(x1,y1)$ и $B(x2,y2)$ вычисляется по формуле:

$d(A,B)=\sqrt{(x_2-x_1{)}^2+(y_2-y_1{)}^2}$​

Центром кластера будем называть точку кластера, сумма расстояний от которой до остальных точек этого кластера минимальна. Антицентром кластера будем называть точку кластера, сумма расстояний от которой до остальных точек этого кластера максимальна.

Входные данные

Файл A: содержит координаты звёзд, расположенных в 2 кластерах, размеры кластеров H=5, W=4, не более 1000 точек.

Файл B: содержит координаты звёзд в 3 кластерах, размеры кластеров H=4, W=5, не более 10 000 точек.
Каждая строка файлов A и B содержит два числа — координаты звезды: сначала по оси x, затем по оси y.

Для каждого файла определите координаты центра и антицентра каждого кластера, затем вычислите два числа: Px​ – среднее арифметическое абсцисс центров кластеров, и Sy​ – среднее арифметическое ординат антицентров кластеров.
В ответе запишите четыре числа: в первой строке сначала целую часть абсолютного значения произведения Px​×10000, затем целую часть абсолютного значения произведения Sy​×10000 для файла А, во второй строке – аналогичные данные для файла B.
Возможные данные одного из файлов иллюстрированы графиком.
Внимание! График приведён в иллюстративных целях для произвольных значений, не имеющих отношения к заданию.
Для выполнения задания используйте данные из прилагаемого файла.