首页 > 代码库 > 最小点对分治法（洛谷1257）
最小点对分治法（洛谷1257）
题目描述
给定平面上n个点，找出其中的一对点的距离，使得在这n个点的所有点对中，该距离为所有点对中最小的
输入样例#1：
31 11 22 2
输出样例#1：
1.0000
首先我们将x坐标排一个序，然后运用分治的思想，分为两块，递归求解两块中的最小点对，但是两块的并集也可能产生点对，但是产生的条件是并集中的两点的距离比d（d是两块中的最小点对）小，所以横纵坐标到中点m的距离也要小于d才能满足要求，我们画图可知，最多只有六个点对应一个点满足要求，所以在时间复杂的上也是o(nlogn)的算法
放上代码吧~
#include<bits/stdc++.h>#define inf 1023901200using namespace std;struct node{double x,y;}s[300000];int t[300000];int n;bool cmp(node a,node b){ return a.x<b.x||(a.x==b.x&&a.y<b.y);}double dis(int a,int b){ return sqrt((s[a].x-s[b].x)*(s[a].x-s[b].x)+(s[a].y-s[b].y)*(s[a].y-s[b].y));}bool comp(int a,int b){ return s[a].y<s[b].y;}double solve(int l,int r){ double d=inf; if(l==r) return d; if(l==r-1) return dis(l,r); int m=l+(r-l)/2; double d1=solve(l,m);//分治求解 double d2=solve(m+1,r); d=min(d1,d2); int k=0; for(int i=l;i<=r;i++) if(fabs(s[m].x-s[i].x)<d)//将横坐标之差小于d的取过来 t[++k]=i; sort(t+1,t+k+1,comp);//注意这里要排序 for(int i=1;i<k;i++) { for(int j=i+1;j<=k&&s[t[j]].y-s[t[i]].y<d;j++)//如果纵坐标也满足要求，注意已经排过序的序列 { double d3=dis(t[j],t[i]); d=min(d3,d); } } return d; }int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%lf%lf",&s[i].x,&s[i].y); sort(s+1,s+n+1,cmp); printf("%.4lf\n",solve(1,n)); return 0;}
最小点对分治法（洛谷1257）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。