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