| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 51 | 44 | 36 | 90.000% |
Супершпион Лэнс Стерлинг находится в городе и отправляется на задание. Для удобства, введем в городе прямоугольную систему координат, единичный отрезок которой имеет длину один метр. Сейчас Лэнс находится в тайном убежище в точке с координатами $(x_s, y_s)$, ему требуется добраться до точки с координатами $(x_t, y_t)$. Он может перемещаться со скоростью один метр в секунду в любом направлении. Однако, он очень проголодался, поэтому решил перед заданием заскочить перекусить.
Всего в городе есть $n$ заведений, в которых Лэнс может пообедать. Заведение номер $i$ находится в точке $(x_i, y_i)$, и Лэнс знает, что он проведет в нем ровно $t_i$ секунд. Помогите ему определить минимальное время, которое потребуется, чтобы добраться до точки назначения, зайдя по пути перекусить в одно из заведений.
В первой строке даны четыре целых числа $x_s$, $y_s$, $x_t$ и $y_t$ --- координаты тайного убежища и точки назначения ($|x_s|, |y_s|, |x_t|, |y_t| \le 1\,000$).
В следующей строке дано одно целое число $n$ --- количество заведений, где Лэнс может пообедать ($1 \le n \le 1\,000$).
В следующих $n$ строках дано по три целых числа $x_i$, $y_i$ и $t_i$ --- координаты $i$-го заведения и количество секунд, которое придется потратить, чтобы пообедать в этом заведении ($|x_i|, |y_i| \le 1\,000$; $1 \le t_i \le 1\,000$).
Выведите одно вещественное число --- минимальное количество секунд, которое потребуется Лэнсу, чтобы добраться из убежища до точки назначения, зайдя по пути перекусить. Ответ будет считаться правильным, если его абсолютная или относительная погрешность не будет превышать $10^{-9}$.
0 0 10 0 1 5 0 3
13.000000000000000
0 -5 0 -3 1 0 5 10
28.000000000000000
0 0 5 5 2 3 3 2 3 4 1
8.236067977499790