TheChroniclesOfAmber
TCO10 Round 3 · 2010-04-11 · by gojira_tc
Problem Statement
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.
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.
{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.
{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.
{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.
{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.
{9111,1906,5286,1832,7221,5984,1975,7007,1329,5219,1779,7262,6696,9427,1289,7558,3568,7972,6935,6283,2598,3560,2456,1726,5618,2624,4227,7640,6758,7323,9429,2906,8925,4130,2071,310,628,4032,1879,9412,8161,9325}
{1615,5883,8995,6724,999,8003,6187,1996,1688,6119,1614,4117,5676,2056,7761,44,6689,3194,3867,7788,5088,1124,6168,6028,4691,3485,2543,9404,6502,3952,6581,4465,4363,5395,6061,1279,7510,1200,843,5719,5053,9757}
{9851,8161,9266,1451,1193,8260,6551,4175,7973,9613,2684,2798,5593,783,3876,1053,6856,8747,7456,7038,4023,723,3803,5538,1864,8254,1752,5089,6671,8485,2473,4757,6255,7700,6834,5647,5918,2056,1231,2137,5403,569}
{9455,2060,6229,4372,4936,9420,91,7408,4395,6401,8517,9683,2068,6652,1077,3867,9859,5314,7597,3521,2516,5623,8979,953,5361,9299,3070,1384,9543,5721,573,8393,9846,4899,5985,5651,22,9223,8584,9952,680,9010}
Returns: 2443.5967343242214
Submissions are judged against all 122 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class TheChroniclesOfAmber with a public method double minimumTime(vector<int> princeX, vector<int> princeY, vector<int> destinationX, vector<int> destinationY) · 122 test cases · 2 s / 256 MB per case