В лаборатории исследуют образцы материалов. Для каждого образца известны координаты x и y его положения на плоскости, масса m, объём V и тип внутреннего строения. Тип обозначается одним из римских чисел от I до VII. Масса и объём положительны; все значения даны в согласованных единицах измерения.
Плотность образца вычисляется по формуле:
ρ = m / V.
Учёный решил разбить все образцы на четыре непересекающихся непустых кластера по значениям плотности. Модуль разности плотностей любых двух образцов одного кластера не должен превышать 0,4. Гарантируется, что такое разбиение существует и единственно.
Центром кластера называется образец этого кластера, для которого сумма модулей разностей его плотности и плотностей всех остальных образцов того же кластера минимальна. Центр каждого кластера единственен.
Входные данные
В каждой строке файла записаны пять значений: x, y, m, V и тип образца. Значения разделены пробелами и/или символами табуляции. Десятичный разделитель — точка. Заголовка и строки с количеством образцов нет.
Количество строк не превышает 10 000. Абсолютные значения всех числовых полей не превышают 100. В каждом кластере есть не менее двух образцов типа IV. Порядок строк не определяет принадлежность образцов кластерам.
Выполните задание
Для каждого кластера определите его центр. Затем найдите два числа:
- P — наибольшее евклидово расстояние между двумя образцами типа IV, принадлежащими одному и тому же кластеру; максимум выбирается среди всех четырёх кластеров;
- Q — наименьшая плотность центра среди центров четырёх кластеров.
Евклидово расстояние между точками A(x1, y1) и B(x2, y2) вычисляется по формуле:
\(d(A, B) = \sqrt{((x_2-x_1)^2 + (y_2-y_1)^2)}\)
В ответе запишите в одной строке два целых числа: сначала целую часть произведения P · 10 000, затем целую часть произведения Q · 10 000. Округлять до ближайшего целого не нужно. Для выполнения задания следует написать программу.
Типовой пример организации данных
1.20 -2.50 5.00000 2 IV
3.40 1.10 7.62000 3 II
-2.00 4.20 16.30000 2 IV
Плотность образца из первой строки примера равна 5 / 2 = 2,5. Пример показывает только формат записи; для решения используйте весь прилагаемый файл.
Формат записи ответа
При решении задания в эмуляторе станции КЕГЭ ответ записывается в таблицу справа. Каждое число в отдельную ячейку: первое число записывается в первую ячейку строки, второе - во вторую ячейку строки.
При решении вне станции в строку ответа вводятся два числа в указанном порядке через один пробел.