외계인

N개의 점이 주어질 때, x = s/2 직선에 대칭이 되도록 추가할 점의 수를 최소로 하는 정수 s를 고르고, 그 점들을 x좌표 오름차순, y좌표 오름차순으로 출력한다. 최소가 여러 개면 가장 작은 s를 쓴다.

보통6해시맵정렬구현기하면접 대비아직 제출이 없습니다시간 제한1초메모리 제한128 MB

문제

외계인과 연락하려고 지구 곳곳에 우주에서도 보이는 거대한 건축물을 세웠다. 15년 동안 1경 쿠나를 쏟아부은 끝에, 연구진은 지구에 지적 생명체가 있다는 사실을 드러내려면 건축물의 배치에 대칭이 있어야 한다는 결론을 내렸다. 계획의 첫 단계는 건축물의 위치를 나타낸 데카르트 좌표계에서 yy축과 평행한 직선을 기준으로 좌우 대칭을 만드는 것이다.

실수 cc에 대해 직선 x=cx = c를 기준으로 대칭이라는 말은, 건축물이 서 있는 모든 좌표 (x,y)(x, y)에 대해 (2cx,y)(2c - x, y)에도 건축물이 서 있다는 뜻이다.

예산은 이미 오래전에 바닥났다. 그래서 새로 짓는 건축물의 수를 최소로 하면서 대칭을 만들어야 한다. 새로 지어야 하는 건축물의 최소 개수와 그 위치를 구하라.

입력

첫째 줄에 이미 서 있는 건축물의 개수 NN이 주어진다. (1N10001 \le N \le 1000)

다음 NN개의 줄에 건축물의 좌표 XXYY가 정수로 주어진다. 두 값의 절댓값은 모두 10810^8보다 작다. 같은 좌표에 서 있는 건축물은 없다.

출력

첫째 줄에 새로 지어야 하는 건축물의 최소 개수 RR을 출력한다.

다음 RR개의 줄에 새로 짓는 건축물의 좌표를 출력한다.

답이 여러 개일 수 있으므로 다음 규칙으로 하나를 정한다. 새 건축물의 좌표도 정수여야 하고, 따라서 대칭축 x=cx = c에 대해 s=2cs = 2c는 정수이다. RR을 최소로 만드는 ss가 여러 개이면 그중 가장 작은 ss를 고른다. 이렇게 정한 축을 기준으로 새로 지어야 하는 좌표를 xx가 작은 순서로, xx가 같으면 yy가 작은 순서로 출력한다.