Final Dash
分而治之
题目
传送门：最小连接
题目大意：
给出二维平面上的N个点，求最近点对的距离。
数据范围：N<=10^5,坐标范围在maxlongint以内。
考察要点：分治
1.把它分成两个或多个更小的问题
2.分别解决每个小问题
3.把各小问题的解答组合起来，即可得到原问题的解答。小问题通常与原问题相似，可以递归地使用分而治之策略来解决
做法
我们考虑把N个点按照x坐标进行排序，然后选择位置在中间的点，以它的x坐标作为分界线，也就是把数组中在它前面的点分到S1集合，其他的分到S2集合中，也就是划分成两个子问题。
然后我们先采用递归的方法先解决S1和S2内部点集的最小距离，然后我们考虑合并S1，S2得到整段的最小距离。
既然S1,S2集合已经被分治解决了，那么我们假设mindist为这两个集合的最小距离中更小的那个，那么S1和S2合并的时候，我们只要考虑会不会有两边的点跨过中间的分界线，它们之间的距离小于mindist就好了。
我们以中间的分界线X为标准，把x坐标在[X-mindist,X+mindist]这个区间的点取出来，因为只有这些点在跨过分界线时可能产生比mindist更小的距离。
接下来我们这么做，把这些点按照y坐标为关键字，从小到大排序，然后我们开始暴力枚举（两重循环）。
但是有一点要注意，我们在第二重的时候判断一下，如果j点和i点的y坐标差距>mindist，直接跳出回到第一重循环。
虽然这看似暴力，但是复杂度是可以保证的。
代码
伪代码：
double getmindist(int l,int r)
if(l>r || l==r) return INF;
if(l+1==r) return dist(p[l],p[r]);
int mid=(l+r)>>1;
double mindist=min(getmindist(l,mid),getmindist(mid,r));
for(i=l;i<=r;i++) if(fabs(p[i].x-p[mid].x)<mindist) np[++top]=p[i];
sort(np+1,np+1+top,cmp);
for(i 1 to top) for(j i+1 to top) if(np[j].y-np[i].y>mindist) break;
else mindist=min(mindist,dist(np[i],np[j]));
return mindist;
}
|
本题代码：
const int maxn=1000001 ;
const int INF=2<<20;
int n,temp[maxn];
struct Point
{
double x,y;
}S[maxn];
bool cmp(const Point &a,const Point &b){
if(a.x==b.x) return a.y<b.y;
else return a.x<b.x;
}
bool cmps(const int &a,const int&b){
return S[a].y<S[b].y ;
}
double min(double a,double b){
return a<b?a:b;
}
double dist(int i,int j){
double x=(S[i].x-S[j].x)*(S[i].x-S[j].x);
double y=(S[i].y-S[j].y)*(S[i].y-S[j].y);
return sqrt(x+y);
}
double merge(int left,int right){
double d=INF;
if(left==right)
return d ;
if(left+1==right)
return dist(left,right);
int mid=(left+right)>>1;
double d1=merge(left,mid);
double d2=merge(mid+1,right);
d=min(d1,d2);
int k=0;
for(int i=left; i<=right; i++)
if(fabs(S[mid].x-S[i].x)<=d) temp[k++]=i;
sort(temp,temp+k,cmps);
for(int i=0;i<k;i++)
for(int j=i+1;j<k&&S[temp[j]].y-S[temp[i]].y<d;j++){
double d3=dist(temp[i],temp[j]);
if(d>d3) d=d3;
}
return d;
}
int main()
{
cin>>n;
for(int i=0; i<n; i++) cin>>S[i].x>>S[i].y;
sort(S,S+n,cmp);
printf("%.3lf\n",merge(0,n-1));
return 0;
}
|
