题目描述
无
样例
无
算法1
(分治) $O(nlognlogn)$
平面最近点问题,采用分治的思想解决。
首先将这些点按横坐标排序。
找到最中间的那个点,发现这个问题的解有三种情况(可任意将中间的点归为左半部分或右半部分)。
1.在这个点的左边存在一对点是该题的解。
2.在这个点的右边存在一对点是该题的解。
3.为该题的解的两个点分别在左边和右边。
于是该题可以分治求解。
递归的求左半部分和右半部分的最近点对,即:要求左半部分的最近点对,就得先将找到左半部分的中间点,再分成两部分,直到l>=r时,return INF,即l>=r为递归边界,将求出来的最短距离记为res,还要考虑上面所说的第三种情况,发现第三种情况的点肯定在横坐标为[mid-res,mid+res]范围内,此时我们可以枚举两个点计算,得到最小值,但此时我们可以剪支,即,先将范围内的点按照纵坐标排序,先从上到下(或者从下到上)找到一个点,记为点A,再从找到的点开始,往下面枚举点,记为点B,如果发现AB的纵坐标之差大于了res,就可以直接去枚举下一个点A。这里有一个问题是,该题有两种点,即发电站和特工,必须是这两种点进行匹配,解决他的方法是,令同种点的距离为INF即可,这样就永远不会取到同种点。
时间复杂度分析:一开始的排序即nlogn,每次分治时要排序,所以还得乘上一个logn,那么在排序之后求解第三种情况是的复杂度如何呢?也就是对与每一个点A最多有几个点B能与之配对,下面是分析:
C++ 代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int INF=0x7fffffff;
struct N1{
double x;
double y;
bool type;
friend bool operator < (N1 a,N1 b){
return a.x<b.x;
}
}point[100200*2],temp[100200*2];
double dist(N1 a,N1 b){//求距离
if(a.type==b.type) return INF;
double dx=a.x-b.x,dy=a.y-b.y;
return sqrt(dx*dx+dy*dy);
}
bool cmp(N1 a,N1 b){
return a.y<b.y;
}
double get_ans(int l,int r){
if(l>=r) return INF;//边界
int mid=(l+r)>>1;
double mid_x=point[mid].x;
double res=min(get_ans(l,mid),get_ans(mid+1,r));
sort(point+l+1,point+1+r,cmp);//按纵坐标排序
int k=0;
for(int i=l;i<=r;++i){
if(point[i].x>=mid_x-res&&point[i].x<=mid_x+res)
temp[++k]=point[i];//只考虑[mid_x-res,mid_x+res]内的点
}
for(int i=1;i<=k;++i){
for(int j=i-1;j>=0;j--){
if(temp[i].y-temp[j].y>=res) break;//剪支,因为已经是排序好的,下面的点肯定不在范围内
res=min(res,dist(temp[i],temp[j]));
}
}
return res;
}
int main(){
int T;
cin>>T;
int N;
while(T--){
cin>>N;
for(int i=1;i<=N;++i) {//输入,把两种类型的点的类型保存为0和1
scanf("%lf%lf",&point[i].x,&point[i].y);
point[i].type=0;
}
for(int i=N+1;i<=N*2;++i){
scanf("%lf%lf",&point[i].x,&point[i].y);
point[i].type=1;
}
sort(point+1,point+1+N*2);//按横坐标排序
printf("%.3lf\n",get_ans(1,N*2));
}
return 0;
}
算法2
(加上归并排序优化) $O(nlogn)$
在递归的过程中就将点按纵坐标排好序,这样每次合并两个已经有序的数组,复杂度为o(n);
C++ 代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int INF=0x7fffffff;
struct N1{
double x;
double y;
bool type;
friend bool operator < (N1 a,N1 b){
return a.x<b.x;
}
}point[100200*2],temp[100200*2];
double dist(N1 a,N1 b){
if(a.type==b.type) return INF;
double dx=a.x-b.x,dy=a.y-b.y;
return sqrt(dx*dx+dy*dy);
}
void merge(int l,int r,int mid){
int i=l;
int j=mid+1;
for(int k=l;k<=r;++k)
if(j>r||(i<=mid&&point[i].y<=point[j].y)) temp[k]=point[i++];
else temp[k]=point[j++];
for(int k=l;k<=r;++k) point[k]=temp[k];
}
double get_ans(int l,int r){
if(l>=r) return INF;
int mid=(l+r)>>1;
double mid_x=point[mid].x;
double res=min(get_ans(l,mid),get_ans(mid+1,r));
merge(l,r,mid);//归并排序
int k=0;
for(int i=l;i<=r;++i){
if(point[i].x>=mid_x-res&&point[i].x<=mid_x+res)
temp[++k]=point[i];
}
for(int i=1;i<=k;++i){
for(int j=i-1;j>=0;j--){
if(temp[i].y-temp[j].y>=res) break;
res=min(res,dist(temp[i],temp[j]));
}
}
return res;
}
int main(){
int T;
cin>>T;
int N;
while(T--){
cin>>N;
for(int i=1;i<=N;++i) {
scanf("%lf%lf",&point[i].x,&point[i].y);
point[i].type=0;
}
for(int i=N+1;i<=N*2;++i){
scanf("%lf%lf",&point[i].x,&point[i].y);
point[i].type=1;
}
sort(point+1,point+1+N*2);
printf("%.3lf\n",get_ans(1,N*2));
}
return 0;
}
关于证明复杂度那里,右边的点如果大于6个的确会出现距离小于res的情况,但是这些点的种类不一定一致啊 有可能不算答案,就比如右边全部都是一种点的情况
1
100000
1 1
1 2
.....
.....
1 100000
3 1
3 2
3 3
…
.....
3 100000
象这种数据 你这2个做法都会超时 。
但是图画的太不用心了最好的题解!!!证明了复杂度,不像其他一样在乱扯,可惜没人看
厉害
真…半圆......