PROBLEM STATEMENT
There is an amazing series of stories called "The Chronicles of Amber" written by Roger Zalazny.
The stories tell us about the princes and princesses of the kingdom of Amber. The princes possess
superhuman abilities and magical artifacts. For example, each prince carries a deck of Tarot
cards, where each trump card has the image of a prince. A prince can contact another prince using
a trump card, and if the second prince agrees, the first prince will teleport instantaneously to
the exact location of the second prince. This teleportation is called a connection, and at any
given time T, only a single connection can happen in the entire kingdom. Note that T is not
necessarily an integer, so if two times, t1 and t2, are different but very close to each other, a
connection can happen at t1 and another connection can happen at t2.
A battle between the forces of Amber and Chaos is about to begin, and each prince of Amber has
been assigned a location where he must be during the battle. The territory where the battle will
occur can be represented as an infinite plane, where locations are points on the plane. The i-th
prince is currently located at point (princeX[i], princeY[i]), but he must be at point
(destinationX[i], destinationY[i]). Princes can travel using two methods: riding, and teleporting
as described above. Princes ride at a speed of 1 distance unit per second. The riding distance
between any two locations is the Euclidean distance between their points. Princes can all ride
simultaneously.
Assume that each prince has a complete deck of Tarot cards and can therefore make a connection
with any other prince. All the princes have united for the sake of the great battle, and will
agree to all connection requests. The princes want to move in such a way that they all reach
their destination points as soon as possible. More precisely, they consider a moment in time, T
(measured in seconds, where the initial time is 0), to be enough for them to reach their
destination points if they can collaborate and organize their riding and/or teleports so that each
of them will be at his respective destination point at exactly moment T. Return the smallest
moment in time, T0, such that all moments T > T0 are enough for them to reach their destination
points.
DEFINITION
Class:TheChroniclesOfAmber
Method:minimumTime
Parameters:vector , vector , vector , vector
Returns:double
Method signature:double minimumTime(vector princeX, vector princeY, vector
destinationX, vector destinationY)
NOTES
-The returned value must have an absolute or relative error less than 1e-9.
CONSTRAINTS
-princeX will contain between 1 and 50 elements, inclusive.
-Each element of princeX will be between 0 and 10000, inclusive.
-princeY will contain the same number of elements as princeX.
-Each element of princeY will be between 0 and 10000, inclusive.
-destinationX will contain the same number of elements as princeX.
-Each element of destinationX will be between 0 and 10000, inclusive.
-destinationY will contain the same number of elements as princeX.
-Each element of destinationY will be between 0 and 10000, inclusive.
EXAMPLES
0)
{1,5,5}
{0,0,0}
{1,1,0}
{4,2,3}
Returns: 4.0
One of the possible scenarios for this testcase is the following. Prince 0 starts riding directly
north toward his destination point while the other two princes remain stationary. When he gets to
point (1,2), prince 1 makes a connection with him and teleports to (1,2), which is prince 1's
destination. When he gets to point (1,3), prince 2 makes a connection with him and teleports to
(1,3). Prince 2 then starts riding west. Prince 0 reaches his destination of (1,4) at the same
time that prince 2 reaches his destination of (0,3).
Note that even though time moment 4 is itself enough for the princes to reach their destination
points, the least T0 satisfying the problem's conditions is still 4.
1)
{0,0,0}
{1,2,3}
{0,0,0}
{0,2,4}
Returns: 1.0
Tarot cards will not help here. Princes 0 and 2 just have to ride to their destination points.
2)
{0,0,0}
{1,2,3}
{0,0,0}
{4,2,0}
Returns: 1.0
The solution is as follows. First prince 1 teleports to prince 2's location, then prince 2
teleports to prince 0's location and finally prince 0 teleports to prince 1's location. After
this, they move directly to their destination points. In this case, each moment T > 1 is enough
for them to reach their destination points, so the correct return value is T0 = 1.
3)
{0,3,5}
{0,4,0}
{3,5,0}
{4,0,0}
Returns: 4.47213595499958
Each prince is located in the other's destination point. The optimal strategy is: prince 2
teleports to prince 0's location, then prince 0 teleports to prince 1's location, and then prince
1 rides to his destination point.
4)
{3629,6751,8655,5115,7809,6759,7133,1810,6102,2539,1777,242}
{5294,180,988,7780,1635,7904,845,7405,4800,2567,4795,2339}
{8723,9275,6705,5875,7981,7666,1158,4135,17,2984,5086,3570}
{6166,53,5980,4499,412,9074,8190,847,650,9158,9116,4396}
Returns: 2622.582696503582
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.