1565_MysteriousMountain

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[0]=y[N+1]=0, 1 ≤ y[i] ≤ 1000 for all 1 ≤ i ≤ 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 (s_i,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 w_i, 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 c_i. They don't want to miss it this time, so the team leader 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 x_i and y_i ( 0 ≤ x_i, y_i ≤ 1000 ) indicating the coordinate of the ith endpoints. in the following N lines, each line contains three intergers c_i, w_i and s_i describing a person ( 1 ≤ c_i < w_i ≤ 100, 0 ≤ s_i ≤ 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

1.43

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: