Canadian Computing Competition: 1997 Stage 2, Day 2, Problem 2

Earth is being attacked by space aliens yet again. The invasion is being tracked by time-lapse photography. Three photographs have been taken at equal time intervals. Your job is to predict the positions of the alien craft in the next photograph, so that they may be intercepted by Earth's defence force. Each alien craft appears as a point of light in the plane of the photograph.

Your input consists of three snapshots of the crafts' positions, taken at $\frac{1}{10}$ second intervals. During these intervals, each craft's speed and direction may be assumed to be constant. Your output consists of the coordinates at which the craft will appear $\frac{1}{10}$ seconds after the third snapshot. (i.e., the positions in the fourth snapshot if there were one.)

Input Specification

The first line contains a positive integer $n$ $(1\le n\le 9)$, the number of points of light in each picture. The next $n$ pairs of lines of input contain the $(x,y)$ $(|x|,|y|<{10}^9)$ coordinates of the points in the first picture, the $x$-coordinate and the $y$-coordinate on the same line. The next $n$ pairs of lines contain the coordinates of the points in the second picture, and the next $n$ pairs of lines contain the coordinates of the points in the third picture. The points in each picture are in no particular order.

Output Specification

Your output is the set of coordinates where the points of light will be $\frac{1}{10}$ seconds after the third picture. Print the number of points, followed by the $(x,y)$ coordinates of each point up to an absolute error of ${10}^{-1}$. If there is more than one solution, output any. If there is no solution, print Impossible.

Sample Input 1

2
1.0 1.0
2.0 2.0
2.0 2.0
3.0 3.0
3.0 3.0
4.0 4.0

Sample Output 1

2
4.0 4.0
5.0 5.0

Sample Input 2

3
1.0 1.0
1.0 2.0
1.0 3.0
2.0 1.5
2.0 2.0
2.0 2.5
3.0 1.0
3.0 2.0
3.0 3.0

Sample Output 2

3
4.0 0.0
4.0 2.5
4.0 3.5

Explanation for Sample Output 2

Note that, for the second test case, another valid solution is $\{(4.0,0.5),(4.0,1.5),(4.0,4.0)\}$.