Sailing You are the newly appointed captain of the HMS Knot Lost, and you need to help your crew back to land. Using your superior astronomy skills you have determined where you are in the ocean with respect to land. As we all know the shore line you are looking to reach can be modeled using parabola in the 2D plane. You know the function that models the parabola and the x y location of the ship currently. Your crew is tired and hungry, so you need to determine the smallest distance needed to travel to reach any part of the shore line. You decided that the program you will make will be able to help many ship quickly in the event of a complete fleet catastrophe. Input Specification The input will begin with an integer q (q 100,000), number of shore/ship pairs. The next q lines will each contain 5 space separated integers, a, b, c, x, and y (1 a 10,000; -10,000 b, c, x0, y0 10,000), representing a different ship scenario. The ship is located at the point (x0, y0). The shoreline will be modeled by the parabola f(x) = ax 2+bx+c. You are guaranteed that the y0 ax0 2+bx0+c. Output Specification For each shore/ship pair output the closest distance between the ship and the shore. You do not need to specify the exact point. Answers with at most 0.000001 absolute or relative error will be treated as correct. For example if the correct answer is 1 billion, then answers between 1,000,001,000 and 999,999,000 inclusive, would be accepted. Input Output Example Input Output 1 1 -4 3 8 2 4.12310562562 3 1 1 1 0 -2 1 0 -1 4 1 4 -10 25 10 10 2.78820252986 2.45853984495 12.3308676174 Explanation Case 1 The ship is at the point (8,2) and the parabola shore is the equation (1)*x2+(-4)*x+(3) The closest point is at (4, 3). The distance of which is sqrt(4*4 + 1*1) = sqrt(17) which is approximately 4.1231056562. Note the parabola above is x2 -4x+3 Case 2 The parabola is x2+x+1 For the first scenario the closest point on the parabola is at approximately (-0.42321621055638575 0.7558957503213213) The parabola is x2 -1 For the second scenario the closest point on the parabola is at approximately (1.647426664594562, 1.714014615217164) The parabola is 4x2 -10x+25 For the final scenario of the second case the landing point is at approximately (1.3724127232591357, 18.80993949926287) Advice Solve the problem of the shortest distance by trying points on the parabola. Different points the on the parabola will have different distances to the ships location. Compute the distances based on these points and search for the optimum point using the ternary search. Grading Information Good comments, whitespace, and variable names 15 points Reads in all the input 5 points No extra input/output (e.g. inputs prompts, Please enter the number of characters:) 10 points Has a function for finding the distance to the parabola based on a given x value 10 points Searches until the range of the search area is small enough for an accurate answer 10 points Your program will be tested on 10 test cases 5 points each No points will be awarded to programs that do not compile using gcc std=gnu11 (gnu eleven). Sometimes a given technique will be requested, and solutions without it will have their maximum point totals reduced. You must use a logarithmic search or receive at most 50 points. Any case that causes your program to return a non-zero error return code will be treated as wrong. Additionally, any case that takes longer than the maximum allowed time (the max between {5 times my runtime, 10 seconds}) will also be treated as wrong. No partial credit will be awarded for a wrong case or a case that crashes.