불완전한 GPS

달리기 경로와 기록 간격 t가 주어질 때, GPS 수신기가 일정 시간마다 위치를 저장하고 직선으로 이어 측정한 거리가 실제 거리에서 몇 퍼센트 줄어드는지 계산한다.

보통5기하시뮬레이션구현수학면접 대비아직 제출이 없습니다시간 제한2초메모리 제한512 MB

문제

달린 거리를 재려고 GPS 수신기를 쓰는 사람이 많다. 그런데 수신기는 완벽하지 않다. 위치를 연속으로 기록하지 않고 정해진 순간에만 저장하므로 실제 경로의 일부를 놓친다. 이 문제의 수신기는 다음과 같이 동작한다.

  • 달리기가 시작되는 시각 0에 출발 위치를 저장한다.
  • 그 뒤로는 tt 시간 단위마다 위치를 저장한다.
  • 달린 시간이 tt의 배수가 아니어도 마지막 시각의 위치는 반드시 저장한다.

수신기는 연속해서 저장한 두 위치 사이를 주자가 직선으로 이동했다고 본다. 그래서 수신기가 계산한 거리는 실제로 달린 거리보다 짧아질 수 있다.

아래 표의 왼쪽은 실제 경로다. 주자는 적힌 시각에 각 위치에 도착했고 시각 11에 달리기를 멈췄다. 수신기가 2 시간 단위마다 위치를 저장하면 오른쪽처럼 기록된다.

시각실제 위치시각기록된 위치
0(0,0)0(0,0)
3(0,3)2(0,2)
5(-2,5)4(-1,4)
7(0,7)6(-1,6)
9(2,5)8(1,6)
11(0,3)10(1,4)
11(0,3)

실제로 달린 거리는 약 14.313708이고 수신기가 잰 거리는 약 11.650281이다. 두 값의 차이는 약 2.663427이며 실제 거리의 약 18.607525%다.

경로의 위치와 시각, 수신기의 기록 간격 tt가 주어진다. 수신기가 놓친 거리가 실제 거리의 몇 퍼센트인지 구하라. 주자는 연속한 두 위치 사이를 일정한 속력으로 직선 이동한다.

입력

입력은 테스트 케이스 하나로 이루어진다. 첫째 줄에 정수 nn (2n1002 \le n \le 100)과 tt (1t1001 \le t \le 100)가 주어진다. nn은 경로에 있는 위치의 개수, tt는 수신기가 위치를 저장하는 간격이며 단위는 초다.

다음 nn개의 줄에는 정수가 세 개씩 주어진다. ii번째 줄의 xix_i, yiy_i (106xi,yi106-10^6 \le x_i, y_i \le 10^6)는 경로의 ii번째 위치의 좌표이고, tit_i (0ti1060 \le t_i \le 10^6)는 주자가 그 위치에 도착하는 시각이며 단위는 초다. tit_i는 증가하는 순서로 주어지고 같은 값이 두 번 나오지 않는다. 첫 위치는 출발점, 마지막 위치는 도착점이므로 t1t_1은 항상 0이다. 실제로 달린 거리는 0보다 크다.

출력

수신기가 놓친 거리가 실제 거리의 몇 퍼센트인지 소수점 아래 넷째 자리에서 반올림해 출력한다. 소수점 아래 자릿수는 정확히 네 자리여야 한다. 예를 들어 18.6075, 0.0000처럼 출력한다.

수신기가 잰 거리는 실제 거리를 넘지 않으므로 답은 음수가 되지 않는다. 놓친 거리가 없으면 음수 0이 아니라 0.0000을 출력한다.