만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

불완전한 GPS

면접 대비

시간 제한2초메모리 제한512 MB

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

보통10점 중 5점

유형
기하, 시뮬레이션, 구현, 수학
정답자
아직 제출이 없습니다

문제

달린 거리를 재려고 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 (2≤n≤1002 \le n \le 100)과 tt (1≤t≤1001 \le t \le 100)가 주어진다. nn은 경로에 있는 위치의 개수, tt는 수신기가 위치를 저장하는 간격이며 단위는 초다.

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

출력

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

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

예제2

  1. 예제 1

    입력
    6 2
    0 0 0
    0 3 3
    -2 5 5
    0 7 7
    2 5 9
    0 3 11
    
    예상 출력
    18.6075
    
  2. 예제 2

    입력
    3 10
    0 0 0
    5 0 5
    0 0 10
    
    예상 출력
    100.0000