有兩個城市想要挖一條運河來運輸產品。兩市的市長邀請著名水利工程師痞子蔡來負責這項工作。由於痞子蔡最近沒有工作,所以馬上就答應了。答應後才發現有很多限制:
這兩市各設有一些集散地(市集),許多產品如蔗糖、稻米等,都會先送到此再作處理;這些集散地已經歷史悠久,地點已經為大家所熟知且不會再更改。這兩市就是希望藉由運河來把產品往外送,但他們對要挖的運河作了一些限制:
為了簡化題目,我們將各集散地視為一個點,也就是沒有面積。其次,我們可以將運河的兩岸視作兩條無限延伸的平行直線。所以現在痞子蔡的任務就是要想辦法,用兩條平行直線將平面上的兩堆點分開。可以參考下面兩個圖:
從上面可以很明顯的看出,雖然兩圖都符合 1. 跟 2. 的限制,但左圖的寬度明顯比右圖還要來得窄,所以我們希望運河長得能像右圖這樣。
現在痞子蔡遇到了麻煩,因為他不知道要如何定出運河的河岸,所以希望你能夠助他一臂之力。
輸入檔包含了多筆的測試資料。每筆測試資料的第一行為兩個正整數 $m, n (1 \le m,n \le 50)$ ,以一個以上的空白隔開,各代表兩市集散地的個數。接下來會有 $m+n$ 行代表集散地的位置,前 $m$ 行(第 $2 \sim m+1$ 行)代表第一個城市的 $m$ 個集散地;後 $n$ 行(第 $m+2 \sim m+n-1$ 行)代表第二個城市的 $n$ 個集散地。這 $m+n$ 行中,每一行都含有兩個浮點數 $x, y$ ,代表此集散地在平面上的坐標 $(x,y) (-1000 \le x,y \le 1000)$ 。這 $m+n+1$ 行就代表著一筆測試資料。
輸入檔以 $m=n=0$ 作為結束。你的程式不需要對這行輸入作處理。
對於每一筆測試資料,依序輸出 (i) 一個浮點數(精確至小數點下第三位),代表運河最大的可能寬度;或是 (ii) 輸出字串 IMPOSSIBLE
,如果無法找到符合規則的運河,或是運河最大的寬度為 $0$。
每一行恰好輸出一筆測試資料的答案。
原TIOJ1041 / NPSC2003初賽(prob D)
No. | Testdata Range | Score |
---|---|---|
1 | 0 | 50 |
2 | 1 | 50 |