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