25544번 - X 만들기 (Hard)

이 문제는 X 만들기 문제와 $N$의 제한을 제외하고 같은 문제이다.

게시판에 $N$개의 압정이 꽂혀 있다. 압정은 매우 작은 크기의 점으로, 게시판은 무한한 크기의 좌표평면으로 표현된다. 알파벳 X를 좋아하는 포닉스는 꽂힌 압정들 중 몇 개를 제거해 남은 압정들이 X자 모양을 만들게 하고 싶다. X자 모양의 정의는 아래와 같다.

• 압정들 중 중심이 되는 압정 $P$가 존재해 아래와 같은 조건을 만족한다.
• $P$와 같은 $x$좌표 또는 $y$좌표를 가지는 압정이 존재하지 않는다.
• $P$를 원점으로 생각했을 때, 한 사분면에 같은 $x$좌표 또는 $y$좌표를 가지는 압정 쌍이 존재하지 않으며 각 사분면에는 압정이 하나 이상 존재해야 한다.
• $P$를 원점으로 생각했을 때, 제1 사분면과 제3 사분면에 위치한 압정들을 $x$좌표 순으로 정렬하면 정렬된 압정들의 $y$좌표는 증가한다.
• $P$를 원점으로 생각했을 때, 제2 사분면과 제4 사분면에 위치한 압정들을 $x$좌표 순으로 정렬하면 정렬된 압정들의 $y$좌표는 감소한다.

포닉스를 위해 압정들의 위치가 주어질 때 남은 압정들이 X자 모양을 이루도록 제거해야 하는 압정의 최소 개수를 구해 보자.

첫째 줄에 압정의 개수 $N$이 주어진다. $(1 \leq N \leq 100\,000)$

둘째 줄부터 $N$개의 줄에 걸쳐 $i$번째 압정의 위치 $x_i$, $y_i$가 주어진다. $(-10^9 \leq x_i, y_i \leq 10^9)$

주어지는 좌표는 모두 정수이며, 같은 좌표를 가진 압정 쌍이 존재하지 않음이 보장된다.

남은 압정들이 X자 모양을 이루도록 제거해야 하는 압정의 최소 개수를 출력한다. 만약 주어진 압정들로 X자 모양을 만들 수 없는 경우 -1을 출력한다.