액세스 포인트

시간 제한1초메모리 제한512 MB

요약

각 팀을 ID 순서대로 두 좌표가 모두 감소하지 않도록 배치해, 고정된 접속 지점까지의 제곱 거리 합을 최소화한다.

난이도: 어려움10점 중 8점
유형: 동적 계획법, 분할 정복, 그리디, 기하
정답자: 아직 제출이 없습니다

문제

한 유명 프로그래밍 대회가 팀을 배치하는 새로운 방식을 검토하고 있다. 대회에 참가하는 $n$ 개의 팀은 무한히 큰 체육관 안의 어떤 위치 $(x, y)$ 에 배정되어야 한다. 팀을 한눈에 파악하기 위해 다음과 같은 전략을 사용한다.

모든 팀에는 $[1, n]$ 범위의 서로 다른 정수 ID가 부여되어 있다. ID가 $i$ 와 $j$ 인 두 팀( $i < j$ )은 각각 위치 $(x_i, y_i)$ , $(x_j, y_j)$ 에 배치되어 $x_i \le x_j$ 이고 $y_i \le y_j$ 여야 한다.

안타깝게도 누군가가 각 팀의 인터넷 액세스 포인트를 이미 (고정된 위치에) 배정해 두었다. 액세스 포인트는 꽤 크고 포트가 하나뿐이라, 서로 다른 팀의 액세스 포인트는 서로 다른 위치에 있다. 모든 팀은 자신에게 지정된 액세스 포인트에 UTP 케이블로 직접 연결되어야 한다. 길이가 $\ell$ 인 UTP 케이블의 비용은 $\ell^2$ 이다.

두 축을 따라 팀의 순서가 유지되면서 필요한 UTP 케이블의 총비용이 최소가 되도록 모든 팀의 위치를 정하라. 심사위원들은 프라이버시에 크게 신경 쓰지 않으므로, 두 개 이상의 팀이 정확히 같은 위치에 있거나 아주 가까이 있어도 괜찮다. 예시는 그림 A.1을 참고하라.

그림 A.1: Sample Input 1의 최적 배치를 나타낸 그림. 팀 위치(상자), 액세스 포인트(원), 필요한 UTP 케이블(점선).

입력

입력은 다음과 같다.

정수 $n$ ( $1 \le n \le 10^5$ )이 있는 한 줄. $n$ 은 팀의 수이다.
$n$ 개의 줄이 이어지며, $i$ 번째 줄에는 정수 $s_i, t_i$ ( $1 \le s_i, t_i \le 10^6$ )가 있다. 이는 $i$ 번 팀의 인터넷 액세스 포인트 위치이다.

어떤 두 액세스 포인트도 같은 위치에 있지 않다.

출력

최적의 합법적인 배치에서 팀을 액세스 포인트에 연결하는 데 필요한 모든 UTP 케이블의 총비용의 최솟값을 출력한다.

답의 절대 오차 또는 상대 오차는 $10^{-6}$ 이하여야 한다.

예제2

예제 1
입력
```
6
4 1
2 4
3 2
8 3
5 6
2 5
```
예상 출력
```
22.5
```
예제 2
입력
```
6
11 6
23 7
24 11
24 32
27 38
42 42
```
예상 출력
```
0
```