首页 > 代码库 > hdu 4353 统计点在三角形内的个数
hdu 4353 统计点在三角形内的个数
Finding Mine
Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 1120 Accepted Submission(s): 298
Problem Description
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.
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.
Input
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.
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.
Output
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.
Sample Input
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
Sample Output
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 atriangle ( (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.
Author
elfness@UESTC_Oblivion
Source
2012 Multi-University Training Contest 6
题目大意:给一个n可选取的顶点,m个金矿的坐标,求选取一个多边形它的面积与它所含金矿的个数的比值最少,找不到一个含有金矿的多边形的情况输出-1。
解题思路:可以证明一个最小比值的三角形(a/b)与其它三角形合起来形成的多边形肯定要大于a/b(a/b<min{a1/b1,a2/b2,...an/bn}时,a/b<(a+a1+a2..an)/(b+b1+b2+..+bn))。预处理每条直线上方金矿数量,那么三角形所含金矿数就等于abs(num[i][k]-num[i][j]-num[j][k])(画下图就知道了)。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <algorithm> 6 using namespace std; 7 8 const int maxn=505; 9 const double eps=1e-8;10 const double inf=1000000000.0;11 int n,m,num[maxn][maxn];12 struct Point13 {14 int x,y;15 Point(int x=0,int y=0):x(x),y(y) {}16 }a[maxn],b[maxn];17 typedef Point Vector;18 Vector operator -(Vector A,Vector B){return Vector(A.x-B.x,A.y-B.y);}19 int Cross(Vector A,Vector B){ return A.x*B.y-A.y*B.x;}//叉积20 inline double min(double a,double b){return a<b?a:b;}21 bool compx(Point a,Point b){return a.x<b.x;}22 23 void init()24 {25 for(int i=0;i<n;i++)26 {27 for(int j=i+1;j<n;j++)28 {29 int temp=0;30 for(int k=0;k<m;k++)31 if(a[i].x<=b[k].x && b[k].x<a[j].x && Cross(a[j]-a[i],b[k]-a[i])>0)32 temp++;33 num[i][j]=temp;34 }35 }36 }37 38 int main()39 {40 int i,j,k,t,icase=0;41 scanf("%d",&t);42 while(t--)43 {44 scanf("%d%d",&n,&m);45 for(i=0;i<n;i++) scanf("%d%d",&a[i].x,&a[i].y);46 sort(a,a+n,compx);47 for(i=0;i<m;i++) scanf("%d%d",&b[i].x,&b[i].y);48 init();49 double ans=inf;50 for(i=0;i<n;i++)51 {52 for(j=i+1;j<n;j++)53 {54 for(k=j+1;k<n;k++)55 {56 int temp=abs(num[i][k]-num[i][j]-num[j][k]);57 if(temp==0) continue;58 ans=min(ans,fabs(Cross(a[j]-a[i],a[k]-a[i])/2.0)/temp);59 }60 }61 }62 if(fabs(ans-inf)<eps) printf("Case #%d: -1\n",++icase);63 else printf("Case #%d: %.6lf\n",++icase,ans);64 }65 return 0;66 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。