Loading [MathJax]/jax/element/mml/optable/SuppMathOperators.js

Задача Q. Border ratio

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб

Условие

Пусть на некотором наборе точек X={xi}ni=1, xiRm задана функция f:RmN. Требуется написать программу, вычисляющую значение border ratio α(x)=ˆxy2xy2,xX, где y=argminyX,f(x)f(y)xy2, ˆx=argminˆxX,f(x)=f(ˆx)ˆxy2.

Формат входных данных

Первая строка входного файла содержит натуральные числа n,m — количество точек и размерность пространства соответственно. В следующих n строках содержится m вещественных чисел и одно натуральное число — координаты точки и значение функции в этой точке.

Формат выходных данных

Выходной файл должен содержать n вещественных чисел — значения border ratio каждой точки с точностью не менее трёх знаков после запятой.

Ограничения

6

2\leqslant m\leqslant 50

Примеры тестов

Стандартный вход Стандартный выход
1
6 2
0 0 0
0 2 1
1 2 0
4 2 1
3 0 1
4 0 0
0.5 1.0 1.0 0.5 1.0 1.0
2
10 2
0 0 0
0 2 0
4 2 0
6 2 0
4 4 1
6 1 1
6 6 1
0 5 2
0 6 2
0 7 2
0.6 1.0 1.0 1.0 1.0 1.0 0.25 1.0 0.75 0.6

0.072s 0.011s 13