유라시아 합중국

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

요약

x좌표 순으로 정렬한 N개의 점을 최대 K개의 연속한 구역으로 나누어, 각 구역의 가장 먼 두 점 거리 제곱의 최댓값을 최소화한다.

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

문제

서기 5013년, 유라시아 대륙을 정복한 황제가 유라시아 합중국을 세웠다. 합중국은 대륙 전체를 차지할 만큼 넓고 인구가 많아서, 황제는 영토를 지방으로 나누어 효율적으로 관리하려고 한다. 합중국에는 주택이 $N$ 채 있고, $i$ 번째 주택은 2차원 유클리드 좌표평면의 $(x_i, y_i)$ 에 있다. 황제는 다음 조건을 만족하도록 주택을 지방에 나누어 맡긴다.

조건 1. 각 지방은 $x$ 좌표가 일정한 구간 안에 들어오는 주택을 관리한다. 이때 어떤 지방이 모든 주택을 관리하거나, 어떤 주택도 관리하지 않을 수 있다.
조건 2. 모든 주택은 정확히 한 지방이 관리해야 한다.
조건 3. 지방은 최대 $K$ 개까지 만들 수 있다.

유라시아 대륙에는 인종, 종교, 민족이 다양하다. 이들 사이의 분쟁을 막으려면 각 지방의 분열을 최대한 줄여야 한다. 어떤 지방의 분열도는 그 지방이 관리하는 주택 중 가장 멀리 떨어진 두 주택 사이의 거리이다. 거리는 유클리드 거리로 잰다. 황제를 도와서 각 지방의 분열도 중 최댓값을 최소로 만들어라.

입력

첫째 줄에 주택의 개수 $N$ 과 지방의 개수 $K$ 가 공백으로 구분되어 주어진다.

다음 $N$ 개 줄 중 $i$ 번째 줄에는 두 정수 $x_i$ , $y_i$ 가 공백으로 구분되어 주어진다. $(x_i, y_i)$ 위치에 주택이 있다는 뜻이다.

출력

각 지방의 분열도 중 최댓값이 가장 작아지도록 나누었을 때 그 최댓값을 $M$ 이라고 하자. $M^2$ 을 출력한다. 좌표가 모두 정수이므로 $M^2$ 도 항상 정수이다.

제한

$1 \le K \le N \le 250\,000$
모든 주택의 좌표는 서로 다르다. 즉 $i \ne j$ 이면 $x_i \ne x_j$ 이거나 $y_i \ne y_j$ 이다.
$0 \le x_i, y_i \le 10^9$

예제2

예제 1
입력
```
4 2
101 100
2 5
100 101
4 3
```
예상 출력
```
8
```
예제 2
입력
```
4 4
3 1
4 1
5 1
9 2
```
예상 출력
```
0
```