불완전한 GPS
면접 대비시간 제한2초메모리 제한512 MB
달리기 경로와 기록 간격 t가 주어질 때, GPS 수신기가 일정 시간마다 위치를 저장하고 직선으로 이어 측정한 거리가 실제 거리에서 몇 퍼센트 줄어드는지 계산한다.
문제
달린 거리를 재려고 GPS 수신기를 쓰는 사람이 많다. 그런데 수신기는 완벽하지 않다. 위치를 연속으로 기록하지 않고 정해진 순간에만 저장하므로 실제 경로의 일부를 놓친다. 이 문제의 수신기는 다음과 같이 동작한다.
- 달리기가 시작되는 시각 0에 출발 위치를 저장한다.
- 그 뒤로는 시간 단위마다 위치를 저장한다.
- 달린 시간이 의 배수가 아니어도 마지막 시각의 위치는 반드시 저장한다.
수신기는 연속해서 저장한 두 위치 사이를 주자가 직선으로 이동했다고 본다. 그래서 수신기가 계산한 거리는 실제로 달린 거리보다 짧아질 수 있다.
아래 표의 왼쪽은 실제 경로다. 주자는 적힌 시각에 각 위치에 도착했고 시각 11에 달리기를 멈췄다. 수신기가 2 시간 단위마다 위치를 저장하면 오른쪽처럼 기록된다.
실제로 달린 거리는 약 14.313708이고 수신기가 잰 거리는 약 11.650281이다. 두 값의 차이는 약 2.663427이며 실제 거리의 약 18.607525%다.
경로의 위치와 시각, 수신기의 기록 간격 가 주어진다. 수신기가 놓친 거리가 실제 거리의 몇 퍼센트인지 구하라. 주자는 연속한 두 위치 사이를 일정한 속력으로 직선 이동한다.
입력
입력은 테스트 케이스 하나로 이루어진다. 첫째 줄에 정수 ()과 ()가 주어진다. 은 경로에 있는 위치의 개수, 는 수신기가 위치를 저장하는 간격이며 단위는 초다.
다음 개의 줄에는 정수가 세 개씩 주어진다. 번째 줄의 , ()는 경로의 번째 위치의 좌표이고, ()는 주자가 그 위치에 도착하는 시각이며 단위는 초다. 는 증가하는 순서로 주어지고 같은 값이 두 번 나오지 않는다. 첫 위치는 출발점, 마지막 위치는 도착점이므로 은 항상 0이다. 실제로 달린 거리는 0보다 크다.
출력
수신기가 놓친 거리가 실제 거리의 몇 퍼센트인지 소수점 아래 넷째 자리에서 반올림해 출력한다. 소수점 아래 자릿수는 정확히 네 자리여야 한다. 예를 들어 18.6075, 0.0000처럼 출력한다.
수신기가 잰 거리는 실제 거리를 넘지 않으므로 답은 음수가 되지 않는다. 놓친 거리가 없으면 음수 0이 아니라 0.0000을 출력한다.