스타라이트 익스프레스

시간 제한2초메모리 제한1024 MB

요약

N개의 역 좌표가 주어질 때, 같은 x 또는 y 좌표를 가진 역끼리 이어진다고 보고 연결된 역 쌍의 수를 가장 많게 만드는 새 역의 좌표를 구합니다.

난이도: 보통10점 중 6점
유형: 해시맵, 유니온 파인드, 그리디
정답자: 아직 제출이 없습니다

문제

무한히 넓은 2차원 좌표평면 위에 $N$ 개의 기차 역이 있다. 각 역에는 1번부터 $N$ 번까지 번호가 붙어 있으며, $i$ 번 역은 $(x_i, y_i)$ 좌표에 있다. 모든 역의 좌표는 서로 다르고, 각 좌표의 절댓값은 $10^9$ 를 넘지 않는다.

각 기차 역에서는 x좌표 또는 y좌표가 같은 다른 역으로 이동할 수 있다. 일련의 이동을 거쳐 한 역에서 다른 역으로 갈 수 있으면 두 역은 연결되어 있다고 한다.

좌표평면 위에 정확히 하나의 역을 더 설치하여 연결되어 있는 역 쌍의 수를 최대화하려고 한다. 설치하는 역의 좌표는 기존 $N$ 개 역의 좌표와 모두 달라야 하며, 기존 역과 같은 좌표 범위 제한을 만족해야 한다. 설치할 좌표를 구하라. 가능한 좌표가 여러 개라면 그중 아무것이나 출력한다.

입력

첫째 줄에 역의 개수 $N$ 이 주어진다. $(3 \le N \le 200\ 000)$

다음 $N$ 개의 줄에는 $i$ 번 역의 좌표 $x_i$ , $y_i$ 가 공백으로 구분되어 주어진다. 주어지는 모든 역의 좌표는 서로 다르다. $(-10^9 \le x_i, y_i \le 10^9)$

출력

설치할 역의 x좌표와 y좌표를 공백으로 구분하여 출력한다. 출력하는 좌표는 이미 있는 $N$ 개 역의 좌표와 모두 달라야 하며, 각 좌표의 절댓값은 $10^9$ 이하여야 한다.

가능한 설치 좌표가 여러 개라면 그중 아무거나 출력한다.

예제2

예제 1
입력
```
5
-1 1
0 1
-2 0
1 2
1 -1
```
예상 출력
```
-1 2
```
예제 2
입력
```
6
-1 1
-1 -1
2 1
2 2
1 -1
0 2
```
예상 출력
```
0 3
```