862
技術社區[雲棲]
POJ 3714 最近點對
題意：給出兩個點的集合，求屬於不同集合的最近點對。
這題是最近點對的變形，在求兩點距離的時候加以判斷是否來自不同集合就行。
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
#define maxn 200005
struct point
{
double x,y;
int f;
} p[maxn],p1[maxn];
int cmpx(point a,point b)
{
return a.x<b.x;
}
int cmpy(point a,point b)
{
return a.y<b.y;
}
double dis(point a,point b)
{
if(a.f!=b.f)
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
return 1e30;
}
double getmin(int l,int r)
{
double ans;
if(l>=r) return 1e30;
if(l+1==r)
return dis(p[l],p[r]);
int m=(l+r)>>1;
ans=min(getmin(l,m),getmin(m+1,r));
int cn=0;
for(int i=l; i<=r; i++)
if(fabs(p[i].x-p[m].x)<ans)
p1[cn++]=p[i];
sort(p1,p1+cn,cmpy);
for(int i=0; i<cn; i++)
for(int j=i+1; j<cn&&p1[j].y-p1[i].y<ans; j++)
ans=min(ans,dis(p1[i],p1[j]));
return ans;
}
int main()
{
int t,n;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(int i=0; i<n; i++)
scanf("%lf%lf",&p[i].x,&p[i].y),p[i].f=0;
for(int i=n; i<n+n; i++)
scanf("%lf%lf",&p[i].x,&p[i].y),p[i].f=1;
sort(p,p+n+n,cmpx);
printf("%.3f\n",getmin(0,n+n-1));
}
return 0;
}
最後更新：2017-04-03 16:48:46