首页 > ACM题库 > HDU-杭电 > HDU 4353-Finding Mine-计算几何-[解题报告]HOJ
2015
05-23

HDU 4353-Finding Mine-计算几何-[解题报告]HOJ

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.

题目:Finding Mine

 

题意:给你n个点,m个金矿点,找一个多边形,使得多边形的面积除以这个多边形内的金矿点个数的比值最小。

思路:其实就是找一个比值最小的三角形就行了,因为其他的三角形的比值都比它大,组合成多边形后势必会将比值变大。可以简短的证明的。

#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;
}

 

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/acdreamers/article/details/9385869