В лесу выделено несколько мест (кластеров), где растёт много деревьев, предназначенных для вырубки. После спиливания дерева его нужно доставить в точку сбора, которая совпадает с одним из деревьев кластера.

Стоимость доставки определяется как расстояние от дерева до точки сбора, умноженное на высоту дерева.   

Расстояние между двумя точками $A(x_1;y_1)$ и $B(x_2;y_2)$ вычисляется по формуле:

 

В каждом кластере нужно найти оптимальную точку сбора (центр) — такую, чтобы суммарная стоимость доставки в это место всех спиленных деревьев данного кластера была минимальна.

Аномалиями назовём совокупности из не более чем \(10\) точек, каждая из которых находится на расстоянии более \(30\) м от точек кластеров. При расчётах аномалии учитывать не нужно.

 

 

Дан входной файл (27_2.txt).

В файле хранятся данные о двух кластерах. Каждый кластер имеет форму прямоугольника размером $100\times 100$ м. Каждая строка файла содержит три характеристики одного дерева: координату \(x\), затем координату \(y\) и затем высоту дерева. Количество деревьев в каждом кластере не превышает \(1000\).

 

Для приведённого файла определи координаты центра каждого кластера, затем вычисли два числа: $P_x$ — среднее арифметическое абсцисс центров кластеров, $P_y$ — среднее арифметическое ординат центров кластеров.

 

В ответе запиши два числа: сначала целую часть произведения $P_x\times 100000$, затем целую часть произведения $P_y\times 100000$.

 

Ответ: