printРабочее место участника

printЗадачи

2423. Ленивый кот

Ограничения: время – 1s/2s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Робокот должен поймать мышей прежде, чем они спрячутся в норках. Для каждой мыши известны её координаты и время до исчезнования. В начальный момент времени кот находится в начале координат (0,0) и может начать двигаться с любой скоростью `V_0` по направлению к любой из мышей. Поймав её, он выбирает любую из оставшихся мышей и мгновенно меняет направление движения, но при этом уже не может изменять скорость, более того – после поимки очередной мыши из-за роста массы скорость кота падает на коэффициент `D`. Например, если до поимки мыши скорость была `V`, то после этого он будет двигаться со скоростью `D*V`, и скорость кота перед поимкой последней мыши будет равна `D^(N-1)*V_0`.
Робокот хочет рассчитать минимальную начальную скорость, которая позволит ему поймать всех мышей.
Первая строка ввода содержит одно целое число – количество мышей `N` (`1\ ≤\ N\ ≤\ 12`). Следующие `N` строк содержат три целых числа – координаты мыши `x_i,\ y_i` (`-1000\ ≤\ x_i,\ y_i\ ≤\ 1000`) и время до исчезновения мыши `t_i` (`1\ ≤\ t_i\ ≤\ 10000`). Последняя строка содержит одно вещественное число с двумя десятичными знаками – коэффициент уменьшения скорости кота после поедания мыши `D` (`0.75\ ≤\ D\ ≤\ 0.99`).
Вывести одно число – минимальную начальную скорость робокота с относительной точностью 0.001 (т.е. если `A` – точный ответ, а `X` – ваш ответ, то `|X-A|<0.001*A`).

Пример ввода

2
4 3 5
5 10 50
.80

Пример вывода

1.000
loading