2015
05-23

# 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 xi,yi(-5000<=xi,yi<=5000), describing the position of the i-th vertex you can choose. Then M lines follow, the i-th line contains two integers xi,yi(-5000<=xi,yi<=5000), describing the position of the i-th mine.

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 xi,yi(-5000<=xi,yi<=5000), describing the position of the i-th vertex you can choose. Then M lines follow, the i-th line contains two integers xi,yi(-5000<=xi,yi<=5000), describing the position of the i-th mine.

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
Hint
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.


#include <iostream>
#include <string.h>
#include <stdio.h>
#include <math.h>
#include <algorithm>

using namespace std;

struct Point
{
int x,y;
bool operator<(const Point &cmp) const
{
return x<cmp.x;
}
};

Point p[210];
Point mine[510];

int cross(Point A,Point B,Point C)
{
return (B.x-A.x)*(C.y-A.y)-(B.y-A.y)*(C.x-A.x);
}

int n,m;
int num[210][510];

void Init(Point a,Point b,int &cnt)
{
int x1=a.x;
int x2=b.x;
for(int i=0;i<m;i++)
if(x1<=mine[i].x&&mine[i].x<x2)
if(cross(a,b,mine[i])>0)
cnt++;
}

int main()
{
int t,cas=1;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)
scanf("%d%d",&p[i].x,&p[i].y);
sort(p,p+n);
for(int i=0;i<m;i++)
scanf("%d%d",&mine[i].x,&mine[i].y);
for(int i=0;i<n;i++)
for(int j=i+1;j<n;j++)
Init(p[i],p[j],num[i][j]=0);
double ans=-1;
for(int i=0;i<n;i++)
{
for(int j=i+1;j<n;j++)
{
for(int k=j+1;k<n;k++)
{
int cnt=num[i][k]-num[i][j]-num[j][k];
if(cnt==0) continue;
double area=cross(p[i],p[j],p[k])/2.0;
double tmp=fabs(area/cnt);
if(ans==-1||tmp<ans) ans=tmp;
}
}
}
printf("Case #%d: ",cas++);
if(ans==-1) puts("-1");
else        printf("%.6lf\n",ans);
}
return 0;
}