(М. Крючков) В лесу выделено несколько мест (кластеров), где растёт много деревьев, предназначенных для вырубки После спиливания дерева его нужно доставить в точку сбора, которая совпадает с одним из деревьев кластера. Стоимость доставки определяется как расстояние от дерева до точки сбора, умноженное на высоту дерева. Под расстоянием понимается расстояние Евклида между двумя точками A(x1, y1) и B(x2, y2) на плоскости, которое вычисляется по формуле: \(d = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}\). В каждом кластере нужно найти оптимальную точку сбора (центроид), такую что суммарная стоимость доставки в это место всех спиленных деревьев данного кластера минимальна. Аномалиями назовём точки, находящиеся на расстоянии более 30 м от точек кластеров. При расчётах аномалии учитывать не нужно.
В файле A хранятся данные о двух кластерах. Каждый кластер имеет форму прямоугольника размером 100 100 м. Каждая строка файла содержит три характеристики одного дерева: координату x, затем координату y и затем высоту дерева. Количество деревьев в каждом кластере не превышает 1000. В файле Б той же структуры хранятся данные о трёх кластерах, каждый из которых имеет вид прямоугольника размером не более 100 200 м. Количество точек в каждом кластере не превышает 10 000.
Для каждого файла определите координаты центра каждого кластера, затем вычислите два числа: Px ‐ среднее арифметическое абсцисс центров кластеров, и Py ‐ среднее арифметическое ординат центров кластеров. В ответе запишите четыре числа: в первой строке сначала целую часть абсолютного значения произведения Px × 100 000, затем целую часть абсолютного значения произведения Py × 100 000 для файла А, во второй строке ‐ аналогичные данные для файла Б.
Исходные данные находятся в файлах 27-26a.txt и 27-26b.txt.