Woburn Challenge 2016-17 Round 4 - Senior Division

"Parking duty? You probably forgot, but I was top of my class at the academy."
"Well then, writing one hundred tickets a day should be easy."
"A hundred tickets… I'm not gonna write a hundred tickets. I'm gonna write two hundred tickets! Before noon!"

Judy Hopps is not pleased about being assigned to parking duty on her first day as an officer of the Zootopia Police Department, but she's still going to give the task her all in order to prove herself.

There are ~N~ ~(1 \le N \le 200\,000)~ parking meters within Judy's assigned area. Representing the area as a Cartesian plane, the ~i~-th meter is located at coordinates ~(X_i, Y_i)~ ~(-1\,000\,000 \le X_i, Y_i \le 1\,000\,000)~, and is going to expire ~T_i~ ~(1 \le T_i \le 1\,000\,000)~ seconds after the start of Judy's shift. No two meters are at the same location, and the meters are given in strictly increasing order of expiration time ~(T_1 < T_2 < \dots < T_N)~.

Judy suspects that none of the parked cars' owners will arrive before their meters expire, but they may move their cars shortly afterwards. As such, if she can be at a meter's location exactly when it expires, she'll be able to write a parking ticket for it! Writing a ticket can be done instantly, so if she's got a fast enough vehicle, she could drive around to visit all ~N~ meters at the appropriate points in time, and end up writing ~N~ parking tickets. However, she's going to take it a little bit easy on her first day – her goal is to write just ~N-1~ parking tickets, meaning that she may skip visiting any single meter of her choice.

At the start of the day, Judy can request a vehicle of her choice from the police department to use throughout the day. There are a variety of vehicles to choose from, with various top speeds, and Judy doesn't want to take a faster vehicle than she needs to get her job done. As such, she'd like to determine the minimum possible top speed of a vehicle which she'd need to be able to write ~N-1~ parking tickets throughout the day. Note that she'll have time before her shift starts to drive to any initial location of her choice.

In test cases worth ~6/14~ of the points, ~N \le 1\,000~.

Input Specification

The first line of input consists of a single integer ~N~.
~N~ lines follow, the ~i~-th of which consists of three space-separated integers ~T_i~, ~X_i~, and ~Y_i~ (for ~i = 1 \dots N~).

Output Specification

Output one line consisting of a single real number, the minimum possible top speed (in units/second) which would allow Judy to write ~N-1~ parking tickets.
Your answer must have no more than ~10^{-5}~ absolute or relative error.

Sample Input

5
10 4 16
14 7 13
20 11 8
23 11 10
24 10 10

Sample Output

1.060660172

Sample Explanation

Using a vehicle with a top speed of ~\sqrt{\frac{18}{4}} \approx 1.060660172~ units/second, Judy can drive from the first meter to the second one in exactly ~4~ seconds, allowing her to be present for each of their expiration times and write two parking tickets. She should then proceed directly to the fourth meter, and then to the fifth one, each with some time to spare. Using this strategy, she'll be able to write ~4~ parking tickets.