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 (x _{i},βy_{i}) and moves with a speed v_{i}.*

*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.*

*Input*

*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 x _{i}, y_{i} and v_{i} (β-β100ββ€βx_{i},βy_{i}ββ€β100, 1ββ€βv_{i}ββ€β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.*

*Output*

*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"))); } } |

π