사영된 배열

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

요약

원점을 중심으로 번호가 적힌 N개의 점을 회전시켜 x축에 투영할 때, 나오는 번호 수열의 역순쌍 수의 최솟값을 구합니다.

난이도: 보통10점 중 7점
유형: 기하, 정렬, 구현
정답자: 아직 제출이 없습니다

문제

2차원 평면 위에 서로 다른 점 $N$ 개가 놓여 있다. 각 점에는 $1$ 부터 $N$ 까지의 서로 다른 정수가 하나씩 쓰여 있다.

이제 모든 점을 원점을 기준으로 특정한 각도만큼 회전시킨 뒤 $x$ 축 위로 사영한다. 그다음 $x$ 좌표가 증가하는 순서대로 점을 읽으면, 점에 쓰인 수로 길이 $N$ 인 수열을 만들 수 있다. 단, 회전 후 두 점이 같은 $x$ 좌표를 가지는 것은 금지된다. 이 방법으로 만들 수 있는 수열 중에서 반전 수가 최소인 수열의 반전 수를 구하시오.

여기서 수열 $A_1, A_2, \cdots, A_n$ 의 반전 수란, $1 \le i < j \le n$ 이면서 $A_i > A_j$ 인 순서쌍 $(i, j)$ 의 개수를 말한다.

입력

첫 번째 줄에 점의 개수 $N$ 이 주어진다. ( $1 \le N \le 2000$ )

다음 $N$ 개의 줄에 걸쳐, $i$ 번째 줄에는 정수 $i$ 가 쓰여 있는 점의 좌표 $x_i$ , $y_i$ 가 공백으로 구분되어 주어진다. ( $1 \le i \le N$ ; $-10^9 \le x_i, y_i \le 10^9$ )

출력

첫 번째 줄에 가능한 최소의 반전 수를 출력한다.

예제1

예제 1
입력
```
5
11 5
1 8
9 7
6 10
4 3
```
예상 출력
```
2
```