AMR12C  Entmoot
Hoo, ho! Good morning, Merry and Pippin!' he boomed, when he saw them. 'You sleep long. I have been many a hundred strides already today. Now we will have a drink, and go to Entmoot.'
'Where is Entmoot?' Pippin ventured to ask.
'Hoo, eh? Entmoot?' said Treebeard, turning round. 'It is not a place, it is a gathering of Ents  which does not often happen nowadays. But I have managed to make a fair number promise to come.'
Indeed, Entmoot cannot be thought of as any particular place, since where it occurs changes from time to time. The choice of the location however, follows a basic principle: Although the Ents (walking and talking Trees  "shepherds of Fangorn Forest") are by and large not hasty, when it comes to gathering for Entmoot, they would like to choose a location that ensures all the Ents can reach as soon as possible.
Note however, that the speed they can travel varies from Ent to Ent. Also, although Fangorn Forest has dense overgrowth, with regard to the Ents, the forest poses no obstacles.
You are given the locations of N Ents who have agreed to join in for Entmoot, as well as their speeds. You need to find out where Entmoot will occur. Formally, given the (x_i,y_i) along with speed s_i for each Ent, find the point (X, Y) such that the maximum time taken by any of the Ents to reach (X, Y) is minimized. Output the earliest time when all the Ents can meet.
Input (STDIN):
The first line contains T, the number of test cases.
The first line of each test case contains N, the number of Ents.
The next N lines contain three spaceseparated integers each. The ith of these lines contains : x_i, y_i, s_i.
Output (STDOUT):
Output one line per test case, containing the earliest time when the Ents can meet. Relative and absolute error of 10^4 are acceptable.
Constraints:
1 <= T <= 10
2 <= N <= 50
1,000,000 <= x_i, y_i <= 1,000,000
1 <= s_i <= 1,000,000
Sample Input:
4
3
0 3 3
4 0 4
3 4 5
3
0 10 2
0 20 2
0 40 2
3
0 100 15
0 100 15
8 0 7
3
0 0 1
10000 0 1
5000 8661 1
Sample Output:
1.000000
7.500000
6.666667
5773.751357
Notes/Explanation of Sample Input:
In the first test case, all the ents can meet at origin in 1 unit of time.
In the second test case, the first and the third ent reach (25,0) after 7.5 units of ime, whereas the second ent reaches there after 2.5 units of time and waits for the remaining ents to arrive.
In the third test case, all the ents can meet at origin in 100/15 units of time.
hide comments
Nikola Herceg:
20140406 18:43:43
Does anybody know how to fix internal error in C++? 

(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†):
20130111 19:24:58
Greedy algorithm doesn't work.. there are some case with local minimum time and global minimum time... I can't solve this problem because of this.. (my algo is greedy)... 

Aakash N S:
20121228 21:02:45
"Relative and absolute error of 10^4 are acceptable."


Islam Diaa:
20121225 02:30:53
I am sure of my solution but do not know why I am getting WA. Are you using validators to check for the relative error? 
Added by:  Varun Jalan 
Date:  20121222 
Time limit:  1s4s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Utkarsh Lath  ICPC Asia regionals, Amritapuri 2012 