ZOJ Problem Set - 1231
A group of M people is chasing a very strange animal. They believe that it will stay on a mysterious mountain T, so they decided to climb on it and have a loot. The mountain looks ordinary, shown below:
That is, the outline of the moutain consists of N+1 segments. The endpoints of them are numbered 0..N+1 from left to right. That is to say, x[i] < x[i+1] for all 0<=i<=n. And also, y=y[n+1]=0, 1<=y[i]<=1000 for all 1<=y<=n.
According to their experience, the animal is most likely to stay at one of the N endpoits numbered 1..N . And... funny enough, they soon discover that M=N, so each of them can choose a different endpoint to seek for the animal.
Initially, they are all at the foot of the mountain. (i.e at (si,0) ) For every person i, he is planing to go left/right to some place (x,0) (where x is an integer - they do not want to take time to work out an accurate place) at the speed of wi, then climb directly to the destination along a straight line(obviously, no part of the path that he follows can be OVER the mountain - they can't fly) at the speed of ci. They don't want to miss it this time, so the teamleader wants the latest person to be as early as possible. How fast can this be done?
The input will contain no more than 10 test cases. Each test case begins with a line containing a single integer N(1<=N<=100). In the following N+2 lines, each line contains two integers xi and yi(0<=xi,yi<=1000) indicating the coordinate of the ith endpoints. in the following N lines, each line contains three intergers ci,wi and si describing a person(1<=ci < wi<=100, 0<=si<=1000) - the climbing speed, walking speed and initial position. The test case containing N=0 will terminate the input and should not be regarded as a test case.
For each test case, output a single line containing the least time that these people must take to complete the mission, print the answer with two decimal places.
In this example, Person 1 goes to (5,0) and climbs to endpoint 2, Person 2 climbs directly to endpoint 3. person 3 goes to (4,0) and climbs to endpoint 1. Shown below:
Source: OIBH Online Programming Contest #1