HDU 4353 Finding Mine

題目連結：http://acm.hdu.edu.cn/showproblem.php?pid=4353

題意：給出n個點，m個點，在n個點中選擇一個多邊形，其中包含的m個點中的點的個數為X，多邊形面積為Y使得Y/X最小？

思路：多邊形為三角形。

int DB(double x)
{
    if(x>EPS) return 1;
    if(x<-EPS) return -1;
    return 0;
}

class point
{
public:
    int x,y;

    point(){}
    point(double _x,double _y)
    {
        x=_x;
        y=_y;
    }

    point operator+(point a)
    {
        return point(x+a.x,y+a.y);
    }

    point operator-(point a)
    {
        return point(x-a.x,y-a.y);
    }

    int operator*(point a)
    {
        return x*a.y-y*a.x;
    }

    point operator*(double t)
    {
        return point(x*t,y*t);
    }

    double operator^(point a)
    {
        return x*a.x+y*a.y;
    }

    point operator/(double t)
    {
        return point(x/t,y/t);
    }

    double getLen()
    {
        return sqrt(x*x+y*y);
    }

    void get()
    {
        RD(x,y);
    }

    int operator==(point a)
    {
        return DB(x-a.x)==0&&DB(y-a.y)==0;
    }

    int operator<(point a)
    {
        if(DB(x-a.x)) return x<a.x;
        return y<a.y;
    }

    point adjust(double L)
    {
        double temp=getLen();
        return point(x*L/temp,y*L/temp);
    }

    void print()
    {
        printf("%.6lf %.6lf\n",x,y);
    }
};

int C,num;

point a[205],b[505];
int n,m,p[205][205];

int cross(point a,point b,point p)
{
    return (b-a)*(p-a);
}

int OK(point a,point b,point p)
{
    return p.x>=a.x&&p.x<b.x&&cross(a,b,p)>0;
}


double area(point a,point b,point c)
{
    return (a*b+b*c+c*a)/2.0;
}

int cmp(point a,point b)
{
    return a.x<b.x;
}

int main()
{
    RD(C);
    while(C--)
    {
        RD(n,m);
        int i,j,k,cnt;
        FOR1(i,n) a[i].get();
        FOR1(i,m) b[i].get();
        clr(p,0);
        sort(a+1,a+n+1,cmp);
        FOR1(i,n) for(j=i+1;j<=n;j++)
        {
            FOR1(k,m) if(OK(a[i],a[j],b[k]))
            {
                p[i][j]++;
            }
            p[j][i]=p[i][j];
        }
        double ans=1e20,temp;
        for(i=1;i<=n;i++) for(j=i+1;j<=n;j++) for(k=j+1;k<=n;k++)
        {
            cnt=abs(p[i][k]-p[j][k]-p[j][i]);
            if(cnt==0) continue;
            temp=fabs(area(a[i],a[j],a[k]))/cnt;
            if(temp<ans) ans=temp;
        }
        printf("Case #%d: ",++num);
        if(ans>1e10) puts("-1");
        else printf("%.6lf\n",ans);
    }
    return 0;
}