시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB53212051.282%

문제

Lots of runners use personal Global Positioning System (GPS) receivers to track how many miles they run. No GPS is perfect, though: it only records its position periodically rather than continuously, so it can miss parts of the true running path. For this problem we’ll consider a GPS that works in the following way when tracking a run:

  • At the beginning of the run, the GPS first records the runner’s starting position at time 0.
  • It then records the position every t units of time.
  • It always records the position at the end of the run, even if the total running time is not a multiple of t.

The GPS assumes that the runner goes in a straight line between each consecutive pair of recorded positions. Because of this, a GPS can underestimate the total distance run.

For example, suppose someone runs in straight lines and at constant speed between the positions on the left side of Table 1. The time they reach each position is shown next to the position. They stopped running at time 11. If the GPS records a position every 2 units of time, its readings would be the records on the right side of Table 1.

Time Position Time Position
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)

Table 1: Actual Running Path on the left, GPS readings on the right.

The total distance run is approximately 14.313708 units, while the GPS measures the distance as approximately 11.650281 units. The difference between the actual and GPS distance is approximately 2.663427 units, or approximately 18.607525% of the total run distance.

Given a sequence of positions and times for a running path, as well as the GPS recording time interval t, calculate the percentage of the total run distance that is lost by the GPS. Your computations should assume that the runner goes at a constant speed in a straight line between consecutive positions.

입력

The input consists of a single test case. The first line contains two integers n (2 ≤ n ≤ 100) and t (1 ≤ t ≤ 100), where n is the total number of positions on the running path, and t is the recording time interval of the GPS (in seconds).

The next n lines contain three integers per line. The i-th line has three integers xi, yi (−106 ≤ xi, yi ≤ 106), and ti (0 ≤ ti ≤ 106), giving the coordinates of the i-th position on the running path and the time (in seconds) that position is reached. The values of ti’s are strictly increasing. The first and last positions are the start and end of the run. Thus, t1 is always zero.

It is guaranteed that the total run distance is greater than zero.

출력

Output the percentage of the actual run distance that is lost by the GPS. The answer is considered correct if it is within 10−5 of the correct answer.

예제 입력 1

6 2
0 0 0
0 3 3
-2 5 5
0 7 7
2 5 9
0 3 11

예제 출력 1

18.60752550117103

출처

ICPC > Regionals > North America > North America Qualification Contest > ACM-ICPC North America Qualifier 2017 H번

  • 문제를 만든 사람: Mike Domaratzki