<a href="https://t.me/+DqUy4L0vu_83ZmE6">(Даня Байт)a> Рассматриваются пункты выдачи заказов одной компании, расположенные в разных районах города.

Каждый ПВЗ обладает следующими характеристиками: координаты на карте города, количество выданных за месяц заказов, средняя стоимость одного заказа, процент комиссии компании, количество сотрудников, а также тип ПВЗ, обозначаемый числами от I до VII (в римской системе счисления).

Компания решила провести кластеризацию ПВЗ по значению месячной выручки компании, то есть разбить их множество на K непересекающихся непустых подмножеств (кластеров), таких, что модуль разности выручек любых двух ПВЗ одного кластера не превышает значения R. Гарантируется, что такое разбиение существует и единственно для заданного R.

Будем называть центром кластера такой его ПВЗ, для которого сумма модулей разности его выручки с выручкой всех остальных ПВЗ этого кластера минимальна.

Для каждого кластера гарантируется единственность его центра.

В каждой строке текстового файла хранится информация об одном ПВЗ: координаты x и y, количество выданных заказов N, средняя стоимость одного заказа P, процент комиссии C, количество сотрудников S и тип ПВЗ.

Значения даны в одинаковых для всех ПВЗ единицах измерения, обозначения единиц измерения в файле не приводятся.

Значения в строке разделяются одним или несколькими пробелами и/или символами табуляции.

Количество строк в файле не превышает 10 000.

Абсолютная величина каждого числового значения не превышает 100,0.

Известно, что все описанные в файле ПВЗ подразделяются ровно на 4 кластера (K=4) с R=2,0 для каждого.

Для каждого кластера определите его центр, затем найдите два числа: Q1 — наибольшее евклидово расстояние между ПВЗ одного кластера, имеющими тип II, и Q2 — максимальное значение выручки среди центров кластеров.

В ответе запишите два числа: сначала целую часть произведения Q1 × 10 000, затем целую часть произведения Q2 × 10 000.

Для справки

Месячная выручка V ПВЗ вычисляется по формуле:

V = (N · P · C) ÷ 100

Евклидово расстояние между двумя ПВЗ на плоскости A(x₁, y₁) и B(x₂, y₂) вычисляется по формуле:

d(A, B) = √((x2 - x1)² + (y2 - y1)²)

Типовой пример организации данных во входном файле

Три строки файла для трёх ПВЗ:

0,67 -2,14 80 25,0 4,0 5 V

3,14 7,22 75 32,0 3,5 4 II

1,33 5,56 90 21,0 4,5 6 IV

Для ПВЗ из первой строки месячная выручка равна:

V = (80・25・4) ÷ 100 = 80

Типовой пример имеет иллюстративный характер.

Для выполнения задания используйте данные из прилагаемого файла.