2D 매트릭스

이 이야기는 매트릭스가 아직 3차원 환상을 만들 만큼 강력한 그래픽 카드를 갖지 못했던 시절을 배경으로 한다. 그래서 사람들은 2차원 세계에 만족해야 했다. 이 2차원 세계에서 매트릭스는 우주를 모형화해야 했다. 우주는 은하들로 이루어지고, 각 은하는 별들로 이루어진다. 안타깝게도 매트릭스의 메모리가 부족해 은하는 단 두 개뿐이었다. 게다가 두 은하를 저장하고 나자 메모리가 모두 소진되어, 각 별이 어느 은하에 속하는지 더는 기억할 수 없게 되었다.

매트릭스는 이 정보를 복원하기 위해 다음 성질을 이용한다. 두 은하는 모두 점대칭이다. 평면 위 점들의 집합이 점대칭이라는 것은, 어떤 중심점 $c$가 존재하여 집합의 모든 점 $p$에 대해 그 반사점 $2c - p$ 역시 집합에 속함을 뜻한다. 이 성질을 이용하면 각 별이 어느 은하에 속하는지 계산할 수 있다.

평면 위에 주어진 점들의 집합을, 두 집합이 모두 점대칭이 되도록 서로소이며 공집합이 아닌 두 집합으로 나누는 프로그램을 작성하라. 가능한 모든 분할을 출력한다. 그러한 분할이 존재하지 않으면 무언가 크게 잘못된 것이므로 MATRIX PANIC을 출력한다.

첫째 줄에 정수 $N$ ($1 \le N \le 150$)이 주어진다. 이어지는 $N$개의 줄 각각에는 $i$번째 별의 좌표를 나타내는 두 정수 $X_i$와 $Y_i$ ($-10^9 \le X_i, Y_i \le 10^9$)가 주어진다. $N$개의 점은 서로 다르다. 주어진 집합은 점대칭이 아님이 보장되므로, 모든 유효한 분할에서 두 은하는 공집합이 아니다.

유효한 분할마다 한 줄씩 출력한다. 하나의 분할은 각 별을 은하 1 또는 은하 2에 배정하는 것이며, 네 수 x1 y1 x2 y2로 나타낸다. 여기서 $(x_1, y_1)$은 은하 1의 중심, $(x_2, y_2)$는 은하 2의 중심이다. 각 은하는 점대칭이므로 그 중심은 유일하게 결정된다.

어떤 분할과, 그 분할에서 은하 1과 은하 2의 이름표만 서로 바꾼 분할은 서로 다른 두 분할로 센다. 따라서 x1 y1 x2 y2와 x2 y2 x1 y1을 모두 출력한다. 출력하는 줄들은 튜플 $(x_1, y_1, x_2, y_2)$의 사전순 오름차순으로 정렬하고, 서로 다른 줄은 한 번씩만 출력한다.

모든 중심 좌표는 항상 정수이거나 정수에 $0.5$를 더한 값이다. 뒤따르는 0 없이 정확히 출력한다(예: 4, 0.5, -1.5). 유효한 분할이 존재하지 않으면 MATRIX PANIC 한 줄을 출력한다.