This page is still under construction.

Parts of this page are still being built. What you see may change.

100 meter dash

Interview

Time limit2sMemory limit1024 MB

Summary
Given GPS points with timestamps and constant speed between them, find the minimum time to cover exactly 100 meters of path along the run.
Level

Medium7 of 10

Topics
Two pointers, Geometry, Math, Implementation
Solved
No attempts yet

Problem

As CS students we sit around all day looking at screens. This is bad for us in many different ways: back pain, need of glasses, and lack of social life. According to the government, regular exercise can help with some of these problems. Although you strongly believe this might not be the case, you have decided to start running, and tracking your runs with the Ztrawa GPS-tracking mobile app.

Ztrawa stores your position coordinates (x,y)(x, y) at some random intervals. When you are done with your run you can look at many different cool stats like your elevation gain, your fastest 100100m, and your average speed from point AA to BB.

Since all CS students are looking to Min-Max everything, you are only interested in your best 100100m over your run. Sadly your Ztrawa app has a bug and the Min-Max feature has stopped working, so you need to work it out yourself.

As Ztrawa only collects a finite amount of data points, we will assume constant speed between two consecutive data points. For example, say you were running around a 400400m track and recorded 66 data points going all around the track and back where you started. This is sample case 11, where we started running from the bottom left, and went around counter-clockwise.

You need to create your own program so you can find what your fastest 100100m was measured in seconds.

Illustration of sample case 11.

Input

The first line contains an integer 1≤n≤1051 \leq n \leq 10^5 indicating the number of readings from Ztrawa. Then follows nn lines containing the information of each reading. The ithi^{\text{th}} such line contains three real numbers xix_i, yiy_i and tit_i, indicating that at the time of reading ii, you were at meter coordinates (xi,yi)(x_i, y_i) relative to where you started, and tit_i seconds has passed since the beginning of the session. It holds that −105≤xi,yi≤105-10^5 \leq x_i, y_i \leq 10^5 for every ii, and 0<t1<t2<…<tn≤1070 < t_1 < t_2 < \ldots < t_n \leq 10^7. All real numbers are given with at most 66 decimal places.

You always start running from (0,0)(0, 0) at time 00.

Output

Output a single real number, how fast you ran the fastest 100m measured in seconds. Anything with an absolute or relative error of 10−410^{-4} will be accepted.

Examples1

  1. Example 1

    Input
    6
    84.39 0 10
    120.89 36.5 14.3
    84.39 73 18.4
    0 73 28.5
    -36.5 36.5 32.7
    0 0 36.95
    
    Expected output
    8.130299066033297