JOIN
Get Time

   Problem Statement  

 Problem Statement for ArmyTeleportation

Problem Statement

    

King Janusz is in great trouble. His enemies have attacked his kingdom from a direction the king did not expect and now he must relocate his troops quickly. The desperate king asked the great sorcerer Mirek for help.

Mirek has three magic towers that are able to teleport troops. Each time a tower is activated, all soldiers get teleported to new locations. The new location is computed by reflecting the old position through the position of the activated tower. (In other words, the activated tower will be in the middle of each segment that connects the old and the new position of a soldier.)

The king can activate the towers in any order he likes. Each tower can be activated arbitrarily many times.

You are given the current locations of the troops in int[]s x1 and y1. For each valid i, there is a soldier on the point (x1[i], y1[i]). You are also given the desired locations of the troops in int[]s x2 and y2. For each valid i, the King wants to have a soldier on the point (x2[i], y2[i]). Finally, you are given the coordinates of the three towers in int[]s xt and yt.

The soldiers are not allowed to move in any way other than by teleportation. The order of soldiers does not have to be preserved. (For example, the soldier that started at (x1[0], y1[0]) may end at (x2[2], y2[2]).)

Return "possible" (quotes for clarity) if it is possible to reach the state in which there are soldiers at all desired locations. Otherwise, return "impossible".

 

Definition

    
Class:ArmyTeleportation
Method:ifPossible
Parameters:int[], int[], int[], int[], int[], int[]
Returns:String
Method signature:String ifPossible(int[] x1, int[] y1, int[] x2, int[] y2, int[] xt, int[] yt)
(be sure your method is public)
    
 

Constraints

-x1, y1, x2 and y2 will have the same number of element which will be between 1 and 50, inclusive.
-xt and yt will have exactly 3 elements each.
-The points described by x1 and y1 are pairwise distinct.
-The points described by x2 and y2 are pairwise distinct.
-The points described by xt and yt are pairwise distinct.
-Each element of x1, y1, x2, y2, xt and yt will be between -1,000,000 and 1,000,000, inclusive.
 

Examples

0)
    
{0, 1}
{0, 1}
{2, 1}
{4, 3}
{2, 3, 2}
{0, 1, 3}
Returns: "possible"
We have soldiers at (0,0) and (1,1). We want to have soldiers at (2,4) and (1,3). There are three towers: at (2,0), (3,1), and (2,3). Mirek can teleport the king's troops as follows:
  1. He will activate the tower at (2,0). One soldier will teleport from (0,0) to (4,0), the other from (1,1) to (3,-1).
  2. He will activate the tower at (3,1), teleporting the soldiers to (2,2) and (3,3).
  3. He will activate the tower at (2,3), teleporting the soldiers to (2,4) and (1,3), as desired.
1)
    
{0, 1, 2}
{2, 4, 6}
{3, 5, 6}
{1, 1, 0}
{3, 1, -2}
{4, 2, 10}
Returns: "impossible"
The soldiers are standing in a line. It is impossible to change that during the teleportation.
2)
    
{0, 1}
{1, 2}
{1, 2}
{2, 3}
{0, 0, 0}
{5, 3, 8}
Returns: "impossible"
Regardless of the order of teleportation, the soldier that starts at (0,1) will always have his x coordinate equal to zero. Therefore he will never reach any of the desired destinations.
3)
    
{6, -5, 1}
{3, -10, -7}
{0, 11, 5}
{-5, 8, 5}
{0, -5, 4}
{-8, -9, -4}
Returns: "possible"
4)
    
{3, 2, 1}
{1, 2, 3}
{4, 5, 6}
{6, 5, 4}
{-2, 5, 6}
{1, -3, 2}
Returns: "impossible"
5)
    
{903, -970, 404, 563}
{-348, -452, 37, 692}
{3359, 1486, 2860, 3019}
{-416, -520, -31, 624}
{346, -838, 916}
{-541, -717, -348}
Returns: "possible"
6)
    
{4600, 8914, 9330, -193, 5422}
{25, 7650, -7366, -8494, -6574}
{-117326, -121640, -122056, -112533, -118148}
{322619, 314994, 330010, 331138, 329218}
{9523, -7546, -9858}
{-3750, -5347, -3828}
Returns: "impossible"
7)
    
{4514, -67225, -78413, -96468, -58938}
{-22815, -86062, -54529, -87391, 42044}
{259998, 331737, 342925, 360980, 323450}
{912263, 975510, 943977, 976839, 847404}
{23726, -98808, -26788}
{80876, -68160, -13684}
Returns: "possible"

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.

This problem was used for:
       Single Round Match 645 Round 1 - Division I, Level Two