题意:给定N个机器的坐标和N个人的坐标,求最近的 人与机器 的距离,保留三位小数.((N<=100000))
分析:显然是平面最近点对问题.但是不是像模板题那样,本题还有个附加限制,就是要一个点是机器,一个点是人,很好处理,我们直接把2N个点放在一起,用结构体加个标记,只要在最后更新ans时先判断两个点的标记不同就行了.
交题时注意POJ的玄学,如果用G++交最后输出不能用lf,只能用f.然后如果用C++交我这份代码直接编译失败.
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
inline int read(){
int x=0,o=1;char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')o=-1,ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*o;
}
const int N=200005;
struct ppx{
int x,y,id;
}a[N],b[N];
double ans;
inline bool cmpx(const ppx &x,const ppx &y){return x.x<y.x;}
inline double dis(ppx x,ppx y){return sqrt(1.0*(x.x-y.x)*(x.x-y.x)+1.0*(x.y-y.y)*(x.y-y.y));}
inline void msort(int l,int mid,int r){
int i=l,j=mid+1,k=l;
while(i<=mid&&j<=r){
if(a[i].y<=a[j].y)b[k++]=a[i++];
else b[k++]=a[j++];
}
while(i<=mid)b[k++]=a[i++];
while(j<=r)b[k++]=a[j++];
for(int i=l;i<=r;++i)a[i]=b[i];
}
inline void solve(int l,int r){
if(l==r)return;
int mid=(l+r)>>1,x=a[mid].x,k=0;
solve(l,mid);solve(mid+1,r);msort(l,mid,r);
for(int i=l;i<=r;++i)
if(fabs(a[i].x-x)<ans)b[++k]=a[i];
for(int i=1;i<k;++i)
for(int j=i+1;j<=k;++j)
if(b[j].y-b[i].y<ans){
if(b[j].id!=b[i].id)ans=min(ans,dis(b[i],b[j]));
}
else break;
}
int main(){
int T=read();
while(T--){
int n=read();
for(int i=1;i<=n;++i){a[i].x=read();a[i].y=read();a[i].id=1;}
for(int i=1;i<=n;++i){a[n+i].x=read();a[n+i].y=read();a[n+i].id=2;}
n=n*2;sort(a+1,a+n+1,cmpx);ans=dis(a[1],a[n]);solve(1,n);
printf("%.3f
",ans);
}
return 0;
}