2011年8月29日 星期一

11516 - WiFi

大街上的居民開會決定要在他們居住的街上安裝無線網路,讓無線網路環境涵蓋所有住戶,請你幫忙選擇無線網路基地台(AP)的地點,他們希望訊號愈強愈好,但他們購買AP的預算有限,在有限的AP數量之下,使得在「所有房子與其最近的AP之間的距離」中最大值,愈小愈好。

大街是直線的,每間房子的門牌號碼剛好等於與端點的距離,例如123號的住戶,距離大街的起點為123公尺。

Input Specification

輸入的第一列有一個整數表示測試資料的組數。接下來每組測試資料的第一列有兩個正整數 n, m,n 表示居民所購買的AP總數,m 表示住戶總數。接下來的 m 列,每列表示一個住戶的門牌號碼。大街上不超過100,000個住戶,且門牌號碼不超過一百萬。

Sample Input

1
2 3
1
3
10

Output Specification

請每組資料輸出一個數值,表示「所有住戶與其最近的AP間的距離」之最大值,請四捨五入到小數點下一位。

Output for Sample Input

1.0

原文出處

沒有留言:

張貼留言