Processing math: 20%

Задача Q. Border ratio

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

Условие

Пусть на некотором наборе точек X={xi}ni=1, xiRm задана функция f:RmN. Требуется написать программу, вычисляющую значение border ratio α(x)=, где y=\mathop{\mathrm{arg\,min}}\limits_{y\in X,\,f\left(x\right)\ne f\left(y\right)}\left\lVert x-y\right\rVert_2,\ \hat{x}=\mathop{\mathrm{arg\,min}}\limits_{\hat{x}\in X,\,f\left(x\right)=f\left(\hat{x}\right)}\left\lVert\hat{x}-y\right\rVert_2.

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

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

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

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

Ограничения

6\leqslant n\leqslant 1500

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.057s 0.008s 13