그늘을 만드는 원형 우산들 사이에서 자동차에서 공까지 갔다가 돌아오는 데 햇빛 아래 달려야 하는 최소 시간을 구한다. 한 번에 k초까지만 달릴 수 있고 공을 줍는 순간에는 발이 식지 않는다.
어려움8그래프최단 경로기하수학아직 제출이 없습니다시간 제한2초메모리 제한512 MB케빈은 해변에서 아침을 보내고 차로 돌아와 출발하려던 참에 공을 두고 왔다는 사실을 깨달았다. 다행히 공이 어디 있는지는 정확히 기억한다. 문제는 바깥이 몹시 덥다는 것이다. 햇빛이 그대로 내리쬐는 모래는 아주 뜨겁고, 케빈은 뜨거운 모래 위를 한 번에 최대 k초까지만 달릴 수 있다. 뜨거운 모래 위에서 케빈의 속력은 정확히 초속 1미터다.
해변 곳곳에는 파라솔이 흩어져 있다. 파라솔은 모두 완전한 원이고, 그 아래 모래는 시원하다. 케빈은 파라솔에 도착할 때마다 발이 식어서 다시 k초를 달릴 수 있을 때까지 그 자리에서 기다린다. 차에서도 발을 식힐 수 있어서 출발할 때 발은 시원한 상태다. 파라솔 그늘과 차에서 보내는 시간, 그늘 안에서 움직이는 시간은 햇빛 아래 있는 시간으로 세지 않는다.
케빈은 뜨거운 모래 위를 한 번에 k초보다 오래 달리지 않는다. 그래서 두 파라솔 사이가 k미터보다 멀면 그 사이를 달리지 않는다. 공을 집어도 발은 식지 않는다. 마지막으로 들른 시원한 곳에서 공까지 달린 거리와 공에서 다음 시원한 곳까지 달린 거리는 같은 k초 안에서 함께 센다.
케빈이 공을 가져와 차로 돌아오기까지 햇빛 아래에 있어야 하는 최소 시간을 구하라.
첫째 줄에 정수 n, k, x, y가 주어진다. n (0≤n≤100)은 파라솔의 개수, k (1≤k≤100)는 케빈이 뜨거운 모래 위를 한 번에 달릴 수 있는 거리(미터), (x, y) (−100≤x≤100, −100≤y≤100)는 공의 좌표다. 케빈은 차가 있는 (0, 0)에서 출발한다. 케빈과 공은 모두 점으로 본다.
다음 n개 줄에 파라솔이 한 줄에 하나씩 주어진다. 각 줄에는 정수 x, y, r (−100≤x≤100, −100≤y≤100, 1≤r≤100)이 있고, 이 파라솔은 중심이 (x, y)이고 반지름이 r인 원이다.
공, 파라솔, 케빈이 같은 위치에 있을 수도 있다. 길이의 단위는 모두 미터다.
케빈이 햇빛 아래에 있어야 하는 최소 시간(초)을 소수점 아래 10자리까지 반올림해 출력한다. 공을 가져와 차로 돌아오는 것이 불가능하면 -1을 출력한다.