X Marks the Spot
Submit Solution(Code Jam Page)


Fair King Tyrone and his four sons conquered the nation of Carrania. His four sons immediately started to squabble about dividing the land between the four of them. The main point of contention was the gold mines of Carrania - each son wanted to have no fewer gold mines than any other.

Fair King Tyrone soon got tired of the squabbling, especially when he learned the number of mines is 4N, so dividing them should be easy. He gathered his sons, took a map, drew an X on it and declared each son would get one quarter of the nation, with borders defined by the X he drew.

Unfortunately, Fair King Tyrone is a bit shortsighted, and the map he drew on was not a map of Carrania. His first minister quickly hid the map, and now tries to draw an identical X on the map of Carrania so that each son gets the same number of gold mines. Unfortunately all sons saw King Tyrone draw the X, and know the borders should be two perpendicular straight lines - so the minister has to make them so.

Help him! Your task is to draw two perpendicular straight lines such that no gold mine lies on a border, and the borders divide the gold mines equally.


The first line of the input gives the number of test cases, T. T test cases follow. Each test case begins with a number N, describing the number of gold mines each son should get. 4N lines follow, each containing two integers, being the coordinates xi, yi of one of the gold mines. No three gold mines are co-linear.


For each test case, output one line containing "Case #x: xa ya xb yb", where x is the case number (starting from 1), (xa, ya) are the coordinates of the point where the two borders intersect, and (xb, yb) are the coordinates of some other point on the X.

All coordinates must be between -109 and 109, have at most 9 digits after the decimal point, and not use exponential notation. They must be exact: the resulting X will be drawn exactly at these coordinates. You should output IMPOSSIBLE instead if there is no good placement of borders.


1 ≤ T ≤ 20
-106 ≤ xi, yi ≤ 106

Small dataset

1 ≤ N ≤ 10

Large dataset

1 ≤ N ≤ 2500



0 0
1 0
0 1
1 1
1 0
0 1
-1 0
0 -1
Case #1: 0.5 0.5 2 0.5
Case #2: 0 0 -3 -3

Points Correct Attempted
10pt 6 11
29pt 1 4

Subscribe to our newsletter

Join our monthly newsletter and never miss out on new stories and promotions.