| Входной файл: | Стандартный вход | Ограничение времени: | 4 сек | |
| Выходной файл: | Стандартный выход | Ограничение памяти: | 512 Мб | |
| Максимальный балл: | 1 |
В городе Оптике проходит научная конференция. Студенты местного университета были приглашены на конференцию и уже провели несколько часов на ней, при этом сама конференция проходит в большом зале в m-мерном пространстве. Преподаватель, пришедший на конференцию вместе со студентами, решил для каждого участника выяснить минимальное расстояние, на котором он может быть достигнут из позиции другого участника. При этом, чтобы сделать задачу полее интересной, преподаватель решил использовать более интересный способ определения расстояния. Каждому из участников требуется не менее f ∈ N соседей на расстоянии не более ε ∈ R (включая себя), чтобы из его позиции можно было достичь других участников. При этом, расстояние до такого участника не может быть меньше, чем расстояние, на котором могут быть достигнуты ровно f участников. Зная позиции всех участников в зале, помогите преподавателю вычислить это расстояние. Во избежание неопределённости было решено рассматривать участников в том порядке, в котором они указаны в списке, при этом достижимых участников стоит рассмотреть в первую очередь, перед переходом к следующему в списке, и не рассматривать одного и того же участника более одного раза.
При решении задачи разрешено использовать только стандартные библиотеки Python и библиотеку numpy.
Первая строка входного файла содержит числа n, m, ε, f — количество участников конференции, размерность пространства, максимальное достижимое расстояние и минимальное количество соседей. В следующих n строках содержится m вещественных чисел — координаты участников в пространстве.
В первой строке выходного файла выведите n вещественных чисел с точностью не менее 3-x знаков после запятой — расстояние на котором достижим каждый из участников. Во второй строке выведите n целых чисел — индекс участника из которого достижим данный. Если участник не достижим, следует вывести − 1 в обоих случаях. При этом, выводить информацию следует в порядке рассмотрения участников, а не в том порядке, в котором они заданы во входных данных.
50 ⩽ n ⩽ 2500
2 ⩽ m ⩽ 50
0.5 ⩽ ε < ∞
3 ⩽ f ⩽ 15
| № | Стандартный вход | Стандартный выход |
|---|---|---|
| 1 | input.txt | output.txt |
| 2 | input.txt | output.txt |