TopCoder

魔法偽娘帕秋莉
想成為帕秋莉的藍孩子

User's AC Ratio

82.4% (14/17)

Submission's AC Ratio

31.9% (29/91)

Tags

Description

有兩個城市想要挖一條運河來運輸產品。兩市的市長邀請著名水利工程師痞子蔡來負責這項工作。由於痞子蔡最近沒有工作,所以馬上就答應了。答應後才發現有很多限制:
這兩市各設有一些集散地(市集),許多產品如蔗糖、稻米等,都會先送到此再作處理;這些集散地已經歷史悠久,地點已經為大家所熟知且不會再更改。這兩市就是希望藉由運河來把產品往外送,但他們對要挖的運河作了一些限制:

  1. 這運河的兩邊必須平行,而且是直線。
  2. 集散地當然不能在運河內部,不過集散地可以剛好在河岸上;而且同一市的集散地要在河的同一邊,也就是在河的同一側不能同時有兩市的集散地。
  3. 運河當然越寬越好。

為了簡化題目,我們將各集散地視為一個點,也就是沒有面積。其次,我們可以將運河的兩岸視作兩條無限延伸的平行直線。所以現在痞子蔡的任務就是要想辦法,用兩條平行直線將平面上的兩堆點分開。可以參考下面兩個圖:

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

Input Format

輸入檔包含了多筆的測試資料。每筆測試資料的第一行為兩個正整數 $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$ 作為結束。你的程式不需要對這行輸入作處理。

Output Format

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

Sample Input 1

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 1

2.000
0.707
IMPOSSIBLE
IMPOSSIBLE
2.000

Hints

Problem Source

原TIOJ1041 / NPSC2003初賽(prob D)

Subtasks

No. Testdata Range Score
1 0 50
2 1 50

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 500 65536 262144 1
1 500 65536 262144 2