2. Как на ЕГЭ (2). Программирование

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

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

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

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

 

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

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

 

 

Даны два входных файла (файл А.txt и файл Б.txt).

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

В файле Б той же структуры хранятся данные о трёх кластерах, каждый из которых имеет вид прямоугольника размером не более $100\times 200$ м. Количество точек в каждом кластере не превышает 10000.

 

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

 

В ответе запиши четыре числа: в первой строке сначала целую часть произведения $P_x\times 100000$, затем целую часть произведения $P_y\times 100000$ для файла А, во второй строке — аналогичные данные для файла Б.

 

Ответ