基地台 (APCS 2017-03 高級)

為因應資訊化與數位化的發展趨勢，某市長想要在城市的一些服務點上提供無線網路服務，因此他委託電信公司架設無線基地台。某電信公司負責其中 \(N\) 個服務點，這 \(N\) 個服務點位在一條筆直的大道上，它們的位置（座標）係以與該大道一端的距離 \(P[i]\) 來表示，其中 \(i=0 \sim N-1\)。由於設備訂製與維護的因素，每個基地台的服務範圍必須都一樣，當基地台架設後，與此基地台距離不超過 \(R\)（稱為基地台的半徑）的服務點都可以使用無線網路服務，也就是說每一個基地台可以服務的範圍是 \(D=2R\)（稱為基地台的直徑）。現在電信公司想要計算，如果要架設 \(K\) 個基地台，那麼基地台的最小直徑是多少才能使每個服務點都可以得到服務。

基地台架設的地點不一定要在服務點上，最佳的架設地點也不唯一，但本題只需要求最小直徑即可。以下是一個 \(N=5\) 的例子，五個服務點的座標分別是 \(1\)、\(2\)、\(5\)、\(7\)、\(8\)。

0    1    2    3    4    5    6    7    8    9
     ▲    ▲              ▲         ▲    ▲

假設 \(K=1\)，最小的直徑是 \(7\)，基地台架設在座標 \(4.5\) 的位置，所有點與基地台的距離都在半徑 \(3.5\) 以內。假設 \(K=2\)，最小的直徑是 \(3\)，一個基地台服務座標 \(1\) 與 \(2\) 的點，另一個基地台服務另外三點。在 \(K=3\) 時，直徑只要 \(1\) 就足夠了。

輸入格式

輸入有兩行。第一行是兩個正整數 \(N\) 與 \(K\)，以一個空白間格。第二行 \(N\) 個非負整數 \(P[0]\)、\(P[1]\)、……、\(P[N-1]\) 表示 \(N\) 個服務點的位置，這些位置彼此之間以一個空白間格。請注意，這 \(N\) 個位置並不保證相異也未經過排序。本題中，\(K<N\) 且所有座標是整數，因此，所求最小直徑必然是不小於 \(1\) 的整數。

輸出格式

輸出最小直徑，不要有任何多餘的字或空白並以換行結尾。

範例輸入 1

5 2
5 1 2 8 7

範例輸出 1

3

範例輸入 2

5 1
7 5 1 2 8

範例輸出 2

7

評分說明

輸入包含若干筆測試資料，每一筆測試資料的執行時間限制 (time limit) 均為 \(2\) 秒，依正確通過測資筆數給分。其中：

第 1 子題組 10 分，座標範圍不超過 \(100\)，\(1 \le K \le 2\)，\(K < N \le 10\)。

第 2 子題組 20 分，座標範圍不超過 \(1,000\)，\(1 \le K < N \le 100\)。

第 3 子題組 20 分，座標範圍不超過 \(1,000,000,000\)，\(1 \le K < N \le 500\)。

第 4 子題組 50 分，座標範圍不超過 \(1,000,000,000\)，\(1 \le K < N \le 50,000\)。

題目來源

APCS 2017 年 3 月 4 日實作題第 4 題「基地台」。參考 APCS 官方歷屆試題 PDF 與 ZeroJudge c575。