TopCoder

Thumb qz2vnqoblj6vp6q
miku
https://chino.taipei

User's AC Ratio

66.7% (2/3)

Submission's AC Ratio

17.4% (4/23)

Description

有兩個城市想要挖一條運河來運輸產品。兩市的市長邀請著名水利工程師痞子蔡來負責這項工作。由於痞子蔡最近沒有工作,所以馬上就答應了。答應後才發現有很多限制:
這兩市各設有一些集散地(市集),許多產品如蔗糖、稻米等,都會先送到此再作處理;這些集散地已經歷史悠久,地點已經為大家所熟知且不會再更改。這兩市就是希望藉由運河來把產品往外送,但他們對要挖的運河作了一些限制:
(1)這運河的兩邊必須平行,而且是直線。
(2)集散地當然不能在運河內部,不過集散地可以剛好在河岸上;而且同一市的集散地要在河的同一邊,也就是在河的同一側不能同時有兩市的集散地
(3)運河當然越寬越好
為了簡化題目,我們將各集散地視為一個點,也就是沒有面積。其次,我們可以將運河的兩岸視作兩條無限延伸的平行直線。所以現在痞子蔡的任務就是要想辦法,用兩條平行直線將平面上的兩堆點分開。可以參考下面兩個圖:

從上面可以很明顯的看出,雖然兩圖都符合(1)跟(2)的限制,但左圖的寬度明顯比右圖還要來得窄,所以我們希望運河長得能像右圖這樣。
現在痞子蔡遇到了麻煩,因為他不知道要如何定出運河的河岸,所以希望你能夠助他一臂之力。

Input Format

輸入檔包含了多筆的測試資料。每筆測試資料的第一行為兩個正整數m n (1 ≦ m,n ≦ 50),以一個以上的空白隔開,各代表兩市集散地的個數。接下來會有m+n行代表集散地的位置,前m行(第2 ~ m+1行)代表第一個城市的m個集散地;後n行(第m+2 ~ m+n-1行)代表第二個城市的n個集散地。這m+n行中,每一行都含有兩個浮點數x y,代表此集散地在平面上的坐標(x,y) (-1000 ≦ x,y ≦ 1000)。這m+n+1行就代表著一筆測試資料。
輸入檔以m=n=0作為結束。你的程式不需要對這行輸入作處理。

Output Format

對於每一筆測試資料,依序輸出 (i) 一個浮點數(精確至小數點下第三位),代表運河最大的可能寬度;或是 (ii) 輸出字串 IMPOSSIBLE,如果無法找到符合規則的運河,或是運河最大的寬度為0。
每一行恰好輸出一筆測試資料的答案。

Sample Input

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

Sample Output

2.000
0.707
IMPOSSIBLE
IMPOSSIBLE
2.000

Hints

Problem Source

原TIOJ1041 / NPSC2003初賽(prob D)

Subtasks

For Testdata: 0 ~ 0, Score: 50
For Testdata: 1 ~ 1, Score: 50
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 500 65536 65536
1 500 65536 65536