Today, on this sunny Saturday I have decided to code a bit in order not to feel guilty in the evening, when I go out. Or something like this. 🙂
I came across of probably the hardest problem, given in CodeForces.com as a first problem in the second divison. Long story short – we have a coordination system and we have to calculate the closest path between two points. Then we have to give them some priority and give the one with the highest result.
The story looks like this:
Vasiliy lives at point (a, b) of the coordinate plane. He is hurrying up to work so he wants to get out of his house as soon as possible. New app suggested n available Beru-taxi nearby. The i-th taxi is located at point (xi, yi) and moves with a speed vi.
Consider that each of n drivers will move directly to Vasiliy and with a maximum possible speed. Compute the minimum time when Vasiliy will get in any of Beru-taxi cars.
The first line of the input contains two integers a and b ( - 100 ≤ a, b ≤ 100) — coordinates of Vasiliy’s home.
The second line contains a single integer n (1 ≤ n ≤ 1000) — the number of available Beru-taxi cars nearby.
The i-th of the following n lines contains three integers xi, yi and vi ( - 100 ≤ xi, yi ≤ 100, 1 ≤ vi ≤ 100) — the coordinates of the i-th car and its speed.
It’s allowed that several cars are located at the same point. Also, cars may be located at exactly the same point where Vasiliy lives.
Print a single real value — the minimum time Vasiliy needs to get in any of the Beru-taxi cars. You answer will be considered correct if its absolute or relative error does not exceed 10 - 6.
Namely: let’s assume that your answer is a, and the answer of the jury is b. The checker program will consider your answer correct, if 
.
What have I done?
The trick is not to be afraid in working with the coordination system and to “see”, that here the closest way to Vasiliy is the direct way. At first I thought that if the city is a coordination system, then we have streets like square and etc. However, in this case the second test example (see the link to the problem, I did not paste everything) has shown that Vasiliy lives in a desert and the taxi can reach him driving directly to his point. Whatever…
Here is what I did:
- Read the input and write the info for the taxis in a list of lists. (first loop).
- Then in a separate list compute the result of the time, which will be needed for each taxi to reach our hero (second loop).
- Once we have the list with the results simply print the smallest one (C# is good in handling these tasks).
That’s all. Here comes the code:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; class Code_160813_01 { static void Main() { string[] s_input = Console.ReadLine().Split(); int i_point_a = int.Parse(s_input[0]); int i_point_b = int.Parse(s_input[1]); int i_cars_total = int.Parse(Console.ReadLine()); List<List<int>> l_cars_info = new List<List<int>>(); List<double> l_result = new List<double>(); double d_distance; double d_result; for (int i = 0; i < i_cars_total; i++) { List<int> l_3 = new List<int>(); string[] s_input2 = Console.ReadLine().Split(); l_3.Add(int.Parse(s_input2[0])); l_3.Add(int.Parse(s_input2[1])); l_3.Add(int.Parse(s_input2[2])); l_cars_info.Add(l_3); } for (int i = 0; i < i_cars_total; i++) { d_distance = Math.Sqrt(Math.Pow(i_point_a - l_cars_info[i][0],2)+Math.Pow(i_point_b-l_cars_info[i][1],2)); d_distance = d_distance / l_cars_info[i][2]; l_result.Add(d_distance); } d_result = l_result.Min(); Console.WriteLine(d_result.ToString(System.Globalization.CultureInfo.GetCultureInfo("en-US"))); } } |
😀