(Даня Байт) Рассматриваются пункты выдачи заказов одной компании, расположенные в разных районах города.
Каждый ПВЗ обладает следующими характеристиками: координаты на карте города, количество выданных за месяц заказов, средняя стоимость одного заказа, процент комиссии компании, количество сотрудников, а также тип ПВЗ, обозначаемый числами от I до VII (в римской системе счисления).
Компания решила провести кластеризацию ПВЗ по значению месячной выручки компании, то есть разбить их множество на K непересекающихся непустых подмножеств (кластеров), таких, что модуль разности выручек любых двух ПВЗ одного кластера не превышает значения R. Гарантируется, что такое разбиение существует и единственно для заданного R.
Будем называть центром кластера такой его ПВЗ, для которого сумма модулей разности его выручки с выручкой всех остальных ПВЗ этого кластера минимальна.
Для каждого кластера гарантируется единственность его центра.
В каждой строке текстового файла хранится информация об одном ПВЗ: координаты x и y, количество выданных заказов N, средняя стоимость одного заказа P, процент комиссии C, количество сотрудников S и тип ПВЗ.
(Даня Байт) Рассматриваются пункты выдачи заказов одной компании, расположенные в разных районах города.
Каждый ПВЗ обладает следующими характеристиками: координаты на карте города, количество выданных за месяц заказов, средняя стоимость одного заказа, процент комиссии компании, количество сотрудников, а также тип ПВЗ, обозначаемый числами от 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
Типовой пример имеет иллюстративный характер.
Для выполнения задания используйте данные из прилагаемого файла.