Finding Mine

In bitland, there is an area with M gold mines.

As a businessman, Bob wants to buy just a part of the area, which is a simple polygon, whose vertex can only be chosen from N points given in the input (a simple polygon is a polygon without self-intersection). As a greedy man, he wants to choose the part with a lot of gold mines, but unluckily, he is short with money.

Those M gold mines can also be seen as points, but they may be different from those N points. You may safely assume that there will be no three points lying on the same line for all N+M points.

Bob alreadys knows that the price to buy an area is proportional to its size, so he changes his mind. Now he wants to buy a part like this: If the part's size is A, and contains B gold mines, then A/B will be minimum among all the possible parts he can choose. Now, please tell him that minimum number, if all the parts he can choose has B=0, just output -1.

First line of the input is a single integer T(T<=30), indicating there are T test cases.
For each test case, the first line is two integers N(3<=N<=200) and M(1<=M<=500), the number of vertexs and the number of mines. Then N lines follows, the i-th line contains two integers x_i,y_i(-5000<=x_i,y_i<=5000), describing the position of the i-th vertex you can choose. Then M lines follow, the i-th line contains two integers x_i,y_i(-5000<=x_i,y_i<=5000), describing the position of the i-th mine.

For each case, you should output “Case #k: ” first, where k indicates the case number between 1 and T. Then output the minimum A/B(rounded after the sixth decimal place) or -1.

3
3 1
0 0
0 2
3 0
1 1
4 2
0 0
0 5
5 0
2 2
1 2
2 1
3 1
0 0
0 2
2 0
2 2

Case #1: 3.000000
Case #2: 5.000000
Case #3: -1

For the second case, we can choose a polygon ( (0,0),(0,5),(2,2),(5,0) ) with A=10 and B=2, if we choose a
triangle ( (0,0),(0,5),(5,0) ), then A=12.5 and B=2.
For the third case, whatever we choose, we can't have a polygon contain the mines.

elfness@UESTC_Oblivion

2012 Multi-University Training Contest 6