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: | int[], int[], int[], int[] | | Returns: | double | | Method signature: | double minimumTime(int[] princeX, int[] princeY, int[] destinationX, int[] destinationY) | | (be sure your method is public) |
|
| |
|
| |
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 | |
|