古力德星球是一個相當特殊的星球,相異於其他宇宙中的行星,這片星球的形狀是棋盤狀的,並被規劃出許多條快速道路,搭乘銀河穿梭器從宇宙中看起來就像是一個棋盤一樣。在某些快速道路的交叉口,座落著一些城市。在宇宙中看起來,就像是棋盤上的棋子一樣,密密麻麻的城市看起來真的很像一盤棋,而古力德也正以此壯觀的風景聞名於宇宙旅客的傳聞中。
但是,古力德星球最近遭受一個相當大的危機。
在距離古力德星球不遠的地方,有一個隕石群即將要與古力德星球相撞,而科學家群正在思索解決的辦法。最後科學家們決定要開啟一個反磁保護罩,但是古力德星球上的能源並不足以供應可以完整保護整個星球的保護罩,將要用一個圓形的保護罩,將所有城市保護起來。
現在,科學家正在煩惱要在哪裡設置防護罩產生器,這個防護罩產生器可以產生一個半徑為R的保護罩,但是如果R越大,整個防護罩的防護力就會被分散了,所以我們希望這個保護罩能夠儘可能的小,我們就必須要找到最好的位置來擺放我們的產生器。
現在距離隕石墜落還有五個小時,你能想出解決的辦法嗎?
輸入檔中有多組輸入,每組輸入的第一行有兩個整數 N, M (1 ≦ N ≦ 1000,3 ≦ M ≦ N^2)分別代表有古力德星球的大小與古力德星球上的城市個數。接下來有 M 行,每行是一個城市所在的 X, Y 座標,(0 ≦ X, Y ≦ N)。不會有兩個城市在同樣的位子上。遇到 N = M = 0 為檔案結束,不須處理這組輸入。
對每組輸入輸出一行,包含一個數字,代表保護罩最小的半徑,四捨五入到小數點下三位。
※2007/11/09:範例輸入修正。感謝jack。
原TIOJ1093 / NPSC2006初賽(prob B)
No. | Testdata Range | Score |
---|---|---|
1 | 0 | 100 |