poj 3714 - 平面最近点对
程序员文章站
2022-03-30 08:39:23
...
题目链接:点击这里
解题思路:
在原有的分治算法上加上标记,如果标记不同的则计算距离,不然的话就返回无穷大.
用归并排序再可以省下logn
这题要是卡数据不知道有什么更高深的办法.
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int mx = 2e5 + 10;
const double INF = 1.0*1e30;
int n,m;
struct node
{
double x,y;
bool f;
bool operator < (node A)const
{
return x < A.x;
}
}s[mx],kep[mx];
double dist(node A,node B)
{
return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));
}
double divide(int l,int r)
{
if(l==r) return INF;
int mid = (l+r)>>1,tot = 0;
double X = s[mid].x;
double d = min(divide(l,mid),divide(mid+1,r));
for(int i=l,j=mid+1;i<=mid;i++){
while(j<=r&&s[j].y<=s[i].y) kep[tot++] = s[j++];
kep[tot++] = s[i];
}
for(int i=0;i<tot;i++) s[i+l] = kep[i];
tot = 0;
for(int i=l;i<=r;i++){
if(fabs(s[i].x-X)<d)
kep[tot++] = s[i];
}
for(int i=0;i<tot;i++){
for(int j=i+1;j<tot;j++){
if(kep[j].y-kep[i].y>d) break;
if(kep[j].f!=kep[i].f)
d = min(d,dist(kep[i],kep[j]));
}
}
return d;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%lf%lf",&s[i].x,&s[i].y),s[i].f = 0;
for(int i=n+1;i<=2*n;i++) scanf("%lf%lf",&s[i].x,&s[i].y),s[i].f = 1;
sort(s+1,s+1+2*n);
printf("%.3f\n",divide(1,2*n));
}
return 0;
}