보로노이 다이어그램 다시

공집합이 아닌 점 집합 $S$의 보로노이 다이어그램은 "이 위치에서 $S$의 어느 점이 가장 가까운가?"라는 기준으로 평면을 나눈 것이다. 정확히는 점 집합 $\{P_1, P_2, \cdots, P_n\}$에 대해, 점 $K$가 영역 $i$에 속하는 것은 모든 $1 \le j \le n$에 대해 $d(P_i, K) \le d(P_j, K)$가 성립할 때이고 그때에만 해당한다. 일반적인 보로노이 다이어그램은 유클리드 거리를 쓰지만, 이 문제는 맨해튼 거리를 쓴다. $d(X, Y)$는 $X$와 $Y$의 맨해튼 거리이며, x좌표와 y좌표 차이의 절댓값을 더한 값이다. 따라서 $(X_1, Y_1)$과 $(X_2, Y_2)$의 맨해튼 거리는 $|X_2 - X_1| + |Y_2 - Y_1|$이다.

위 그림에서 평면의 모든 위치는 가장 가까운 점의 색으로 칠해져 있다. 하나의 영역에만 속하는 위치는 옅은 색으로, 둘 이상의 영역에 속하는 위치는 검은 선과 점으로 표시된다.

임의의 실수 $R$에 대해, 영역 안에 $d(O, P) > R$을 만족하는 점 $P$가 존재하면 그 영역은 무한 영역이다. 여기서 $O$는 원점이다. 보로노이 다이어그램에서 무한 영역의 개수를 구하라.

첫 줄에 보로노이 다이어그램을 이루는 점의 개수 $N$이 주어진다. 이후 $N$개의 줄에 각각 점 $P_i$의 좌표 $x_i$, $y_i$가 정수로 주어진다.

무한 영역의 개수를 나타내는 정수 하나를 출력한다.

• $1 \le N \le 250\,000$
• $-10^9 \le x_i,\ y_i \le 10^9$ ($1 \le i \le N$)
• $N$개의 점은 모두 서로 다르다.

예제 2에서 겹치는 영역은 두 가지 이상의 색이 감산 혼합된 것으로 표시된다. $(x \ge 5 \wedge y \le 1) \vee (x \le 1 \wedge y \ge 5)$을 만족하는 모든 점은 다섯 영역에 모두 포함되므로 가장 진한 색으로 칠해진다.