스프링클러 최소 반경

문제

농장의 긴 이랑 하나에 N그루의 과수가 심겨 있다. i번 과수의 위치는 이랑의 왼쪽 끝에서 잰 정수 거리 x_i미터이다. 같은 위치에 여러 그루가 있을 수 있고, 위치는 정렬되어 주어지지 않는다.\n농장주는 스프링클러 K대를 이랑 위에 설치하려 한다. 모든 스프링클러는 같은 정수 반경 r을 가지며, 정수 위치 p에 설치한 스프링클러는 p - r 이상 p + r 이하인 위치에 있는 과수에 모두 물을 준다. 설치 위치 p는 과수의 위치와 무관하게 아무 정수나 고를 수 있고 음수여도 된다. 같은 위치에 여러 대를 설치해도 되며, K대를 모두 설치해야 하지만 일부가 불필요해도 상관없다.\n모든 과수가 적어도 한 대의 스프링클러에게서 물을 받도록 설치할 수 있는 최소의 정수 반경 r을 구하시오. 반경이 0이면 스프링클러는 자기 위치의 과수에만 물을 준다. 예를 들어 과수가 위치 1, 2, 10, 11, 20에 있고 K가 2이면, 반경 5로 위치 6과 25에 설치하여 모든 과수에 물을 줄 수 있다.

입력

첫 줄에 N, K가 공백으로 구분되어 주어진다. (1 ≤ K ≤ N ≤ 200000) 둘째 줄에 x_1, ..., x_N이 공백으로 구분되어 주어진다. (0 ≤ x_i ≤ 10^9)

출력

조건을 만족하는 최소 정수 반경 r을 한 줄에 출력한다.

5 2
1 2 10 11 20

5

3 3
7 7 100

0

4 1
3 9 4 1

4

출처: Devin.KR 자체 제작