내부 정점

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

요약

무한 격자에서 행과 열로 둘러싸인 점을 채우는 폐쇄 과정을 시뮬레이션해 최종 검은 점의 개수를 구하거나 종료되지 않음을 판별합니다.

난이도: 어려움10점 중 8점
유형: 기하, 시뮬레이션, 수학
정답자: 아직 제출이 없습니다

문제

무한히 넓은 정사각 격자가 있고, 각 격자점은 검은색 또는 흰색으로 칠해져 있다.

어떤 격자점 $V$ 와 같은 행(가로줄)에 있는 두 검은 격자점이 존재하여 $V$ 가 그 둘 사이에 놓이면, $V$ 를 가로-내부 격자점이라고 한다. 마찬가지로 $V$ 와 같은 열(세로줄)에 있는 두 검은 격자점 사이에 $V$ 가 놓이면 $V$ 를 세로-내부 격자점이라고 한다. 가로-내부이면서 동시에 세로-내부인 격자점을 내부 격자점이라고 부른다.

매 단계마다 흰색인 모든 내부 격자점을 동시에 검은색으로 바꾼다. 나머지 격자점의 색은 그대로 유지된다. 흰색 내부 격자점이 하나도 남지 않으면 과정이 멈춘다.

과정이 멈춘 뒤 검은 격자점의 개수를 구하여라.

입력

첫째 줄에 처음에 검은색인 격자점의 개수 $n$ ( $0 \le n \le 100000$ )이 주어진다.

이어지는 $n$ 개의 줄에는 각각 검은 격자점의 좌표를 나타내는 두 정수가 주어진다. 주어지는 격자점은 모두 서로 다르며, 각 좌표의 절댓값은 $10^9$ 이하이다.

출력

과정이 멈춘 뒤 검은 격자점의 개수를 출력한다. 만약 과정이 멈추지 않으면 -1을 출력한다.

힌트

예제5

예제 1
입력
```
4
0 2
2 0
-2 0
0 -2
```
예상 출력
```
5
```
예제 2
입력
```
1
0 0
```
예상 출력
```
1
```
예제 3
입력
```
2
0 0
5 0
```
예상 출력
```
2
```
예제 4
입력
```
8
0 0
1 0
2 0
0 1
2 1
0 2
1 2
2 2
```
예상 출력
```
9
```

예제 5

입력

예상 출력