Problem D - Finding UFOs

It is known that a certain kind of UFOs are there. They look like a disk and, when they are seen from the bottom side, they present a variable number of thin and thick concentric circles. It is also known that the UFO presenting the largest number of consecutive thick circles is the leader of a group.

Figure 1

Fig. 1 - Three UFOs; the last one, on the right side, is the leader.

One got several images from these UFOs and processed them, trying to know where the leader is located. Unfortunately, the processing system used was able to detect, from each circle line, only the thickness and the (x, y) coordinates of three points. Furthermore, data resulted completely unsorted, so it is now necessary to reconstruct their positions.

The Problem

The problem you have to solve is to evaluate the (x, y) centre coordinates of one UFO group leader. To do it, you will have access to a list of circles, without any order guaranteed. Each circle contains its thickness (0=thin; 1=thick) and the coordinates (x, y) of the detected three points that belong to the circle line.


The first line of the input contains the number of circles defined in the next lines, one circle per line. Each one of the subsequent lines is composed by a character "0" or "1" and a sequence of six decimal values in the order x1 y1 x2 y2 x3 y3. All the values are separated by a space, and can be negative or positive.

The maximum number of circles is 1000 and there may be UFOs with only one circle each. Coordinates of centres are integer values. Circles from different UFOs may overlap.


The output must be a text line containing two integer values corresponding to the resulting coordinates x and y. Remember that these should be the coordinates of the leader UFO. There will always be an unique leader (there will be an UFO with an unique maximum of consecutive thick circles).

Sample Input

1 185.0000 64.0192 200.0000 60.0000 230.0000 90.0000
1 100.0000 50.0000 94.6410 70.0000 80.0000 84.6410
1 70.0000 50.0000 68.6603 55.0000 60.0000 40.0000
0 217.3205 100.0000 180.0000 90.0000 200.0000 110.0000
0 40.0000 50.0000 80.0000 50.0000 60.0000 30.0000
0 90.0000 50.0000 45.0000 75.9808 45.0000 24.0192
0 225.0000 133.3013 243.3013 115.0000 150.0000 90.0000
0 200.0000 100.0000 190.0000 90.0000 210.0000 90.0000
1 180.0000 124.6410 200.0000 130.0000 240.0000 90.0000

Sample Output

200 90

Figure 2

Fig. 2 - The two UFOs of the sample input.

TIUP & CPUP 2007
Universidade do Porto
(30 de Maio de 2007)