시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB57222167.742%

문제

게시판에 $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 3\,000)$

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

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

출력

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

예제 입력 1

9
1 1
1 0
1 -1
0 1
0 0
0 -1
-1 1
-1 0
-1 -1

예제 출력 1

4

(1,0), (0,1), (-1,0), (0,-1)에 위치한 압정들을 제거하면 남은 압정들이 X자 모양을 이룬다.

예제 입력 2

5
0 0
1 0
2 0
-1 0
-2 0

예제 출력 2

-1

주어진 압정들로 X자 모양을 만들 수 없다.

출처

University > POSTECH > 2022 POSTECH Programming Contest B번