AMR12C - Entmoot

no tags 

 

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 space-separated 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.

 

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 space-separated 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: 2014-04-06 18:43:43

Does anybody know how to fix internal error in C++?

(Tjandra Satria Gunawan)(曾毅昆): 2013-01-11 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: 2012-12-28 21:02:45

"Relative and absolute error of 10^-4 are acceptable."
Is it really so? Also, how many digits do we need to print after the decimal point?

Islam Diaa: 2012-12-25 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:2012-12-22
Time limit:1s-4s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Utkarsh Lath - ICPC Asia regionals, Amritapuri 2012