Uphill and Gahui
InterviewTime limit1sMemory limit256 MB
Given a polyline of checkpoints and two query positions, output the absolute average slope between them as a reduced fraction.
- Level
Medium4 of 10
- Topics
- Geometry, Math, Implementation
- Solved
- No attempts yet
Problem
Gahui is a cyclist who enjoys uphills and downhills. Gahui plans to start at a starting point with position X0 and height H0 and ride through N checkpoints, each with its own position Xi and height Hi. The checkpoints are numbered 1, 2, 3, ..., N in order of increasing horizontal distance from the starting point, and adjacent checkpoints, including the starting point, are connected to each other by straight line segments.

For safe riding, Gahui wants to check the average slope of each segment, so that she can plan where and how hard to apply her brakes. With dozens of checkpoints on her route, this checking is a huge chore. Write a program that, given the start position and end position of a segment Gahui wants to check, finds the average slope of that segment and helps Gahui!
Input
The first line gives the number of checkpoints N (1 ≤ N ≤ 50).
The second line gives the position X0 and height H0 of the starting point, separated by a space. The position of the starting point is always 0.
From the third line to the N+2-th line, each line gives the position Xi and height Hi of checkpoint i, separated by a space. All positions and heights given, including that of the starting point, are integers between 0 and 5,000 inclusive, and always satisfy Xi-1 < Xi (where i ≠ 0).
The N+3-th line gives the start position S and end position E of the segment Gahui wants to check. (X0 ≤ S < E ≤ Xn)
Output
Print the absolute value of the average slope of the segment Gahui wants to check. If this value is an integer, print the integer; otherwise, print it as a reduced fraction of the form p/q.