100 meter dash
InterviewTime limit2sMemory limit1024 MB
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 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 m, and your average speed from point to .
Since all CS students are looking to Min-Max everything, you are only interested in your best m 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 m track and recorded data points going all around the track and back where you started. This is sample case , 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 m was measured in seconds.

Illustration of sample case .
Input
The first line contains an integer indicating the number of readings from Ztrawa. Then follows lines containing the information of each reading. The such line contains three real numbers , and , indicating that at the time of reading , you were at meter coordinates relative to where you started, and seconds has passed since the beginning of the session. It holds that for every , and . All real numbers are given with at most decimal places.
You always start running from at time .
Output
Output a single real number, how fast you ran the fastest 100m measured in seconds. Anything with an absolute or relative error of will be accepted.