Time Limit: 1000 ms Memory Limit: 65536 KiB
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.
3 0 0 3 4 6 1 12 6 16 0 2 4 4 8 10 15 4 25 14 0
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: