219
HDU 4353 枚举
题意：给出n个点，为商人要购买的点，m个点为金矿的位置。问如何使够买三个点或三个以上的点围成的多边形面积与多边形内金矿的数量的比值最小。
这题很容易想到比值最小的肯定是三角形和在三角形内的点的数量想比。虽然我没想到。然后很容易想到四重循环来找最小的比值但是会超时，所以需要预处理一下，先把两组点按照x轴排序，枚举两个n点，针对于每组点组成的线段选线段正上方的m点，存入数组中。然后再进行n^3循环枚举3个n内的点，长线段上的m点数-两条短线段的m点数的绝对值就是三角形内的点数。为什么是绝对值，因为长线短可能在上面，可能在线面，然后注意预处理时要注意区间的边界。828ms
#include <iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
struct point
{
int x,y;
};
int cmp(point a,point b)
{
return a.x<b.x;
}
int Direction(point pi,point pj,point pk) //判断向量PiPj在向量PiPk的顺逆时针方向 +顺-逆0共线
{
return (pj.x-pi.x)*(pk.y-pi.y)-(pk.x-pi.x)*(pj.y-pi.y);
}
int yl[205][205];
point data[205],mine[505];
int main()
{
int t,n,m,ca=0;
scanf("%d",&t);
while(t--)
{
memset(yl,0,sizeof(yl));
scanf("%d%d",&n,&m);
for(int i=0; i<n; i++)
scanf("%d%d",&data[i].x,&data[i].y);
for(int i=0; i<m; i++)
scanf("%d%d",&mine[i].x,&mine[i].y);
sort(mine,mine+m,cmp);
sort(data,data+n,cmp);
for(int i=0; i<n; i++) //预处理
for(int j=i+1; j<n; j++)
for(int k=0; k<m&&mine[k].x<data[j].x; k++)
if(mine[k].x>=data[i].x&&Direction(data[i],data[j],mine[k])>0)
yl[i][j]++;
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 q=yl[i][k]-yl[i][j]-yl[j][k];
if(q!=0)
{
double p=fabs((double)Direction(data[i],data[j],data[k])/(2.0*double(q)));
if(p<ans||ans==-1) ans=p;
}
}
printf("Case #%d: ",++ca);
if(ans!=-1)
printf("%.6f\n",ans);
else
puts("-1");
}
return 0;
}
最后更新：2017-04-03 16:48:36