Roller coaster velociraptor P78006


Statement
 

pdf   zip

thehtml

You are going to get on a roller coaster when you realize that a velociraptor is coming straigh at you. Fortunately, you have a way to escape: the roller coaster. You know that the velociraptor can follow you through the rail, but he will not fit in the tunnel of the roller coaster. You start to push the car in the platform while the velociraptor is chasing you. For obvious reasons you want to get on the car as soon as possible: you want to obtain the speed enough to reach the tunnel and get rid of the velociraptor, but you do not want to push more than the strictly needed in case it catches you in the platform.

You know all the rises and way down that the roller coaster has. Moreover, you know that for each metre in vertical that goes up, the car loses a speed of K kilometres per hour, while for each metre in vertical that goes down, recovers the same lost speed of K kilometres per hour (the laws of physics are not fulfilled in theme parks; if not, it would not have any sense paying so much for the ticket). You also know that there is not any friction with the rail, and that is possible that the car has speed 0 during some moment of the route (you can gather momentum and car would continue) but at any moment it can have negative speed.

Input

The first line of the test data contains the number of cases to solve. Each case starts with 3 integers N, X and K in a line, where N is the number of stretches of the roller coaster, X is the coordinate x of the point where the tunnel is, and K is the speed in kilometres per hour that is lost (respectively, is won) for each metre gone up (respectively, gone down) in vertical. The following N+1 lines contain N+1 pairs of coordinates (xi,yi), separated by a space, that describe the extremes of the N straight stretches that the attraction is composed of. It is fulfilled that (x1,y1) is always (0,0), and that the xi are stricly increasing that is, xi < xi+1. Moreover, the tunnel always is in the beginning of a stretch of the roller coaster, that is, exists a point xi with 1<i≤ N such that xi = X.

Output

For each case, your program must print in a line the minimal speed in kilometres per hour which you have to leave the platform with to reach the beginning of the tunnel, assuring that during the whole route the speed of the car is greater or equal than 0.

Scoring

  • TestA:  ‍ Tests with no more than 20 cases where N ≤ 15 and X ≤ 1000.  ‍30 Points ‍
  • TestB:  ‍ Tests with no more than 20 cases where N ≤ 25000 and X ≤ 106.  ‍70 Points ‍
Public test cases

  • Input

    5
5 51 10
0 0
2 97
51 11
67 -85
148 -116
214 -68
5 87 19
0 0
87 -79
124 -170
167 -221
197 -146
205 -230
5 35 15
0 0
35 -33
132 -10
141 -64
178 -97
226 -126
5 249 7
0 0
77 -46
132 -96
182 -107
249 -184
329 -212
5 196 7
0 0
37 -7
97 8
183 40
196 126
280 58

    Output

    970
0
0
0
882

  • Input

    2
2 10 7
0 0
10 0
20 0
4 30 7
0 0
10 10
20 10
30 0
40 0

    Output

    0
70
    • Information
    Author
    Ricardo Martin
    Language
    English
    Translator
    Carlos Molina
    Original language
    Spanish
    Other languages
    Spanish
    Official solutions
    C++
    User solutions
    C++