邢台企业做网站费用,建立自己网站要多少钱,商业网线多少钱一年,佛山骏域网站建设专家最近点问题#xff1a;二维平面中有n#xff08;n很大#xff09;个点#xff0c;求出距离最近的两个点思路#xff1a;因为n的值很大#xff0c;所以暴力和dp都行不通了吧#xff01;分治法就挺好的。将区间一半一半的分开#xff0c;直到分成只有一个点或两个点的时候… 最近点问题二维平面中有nn很大个点求出距离最近的两个点思路因为n的值很大所以暴力和dp都行不通了吧分治法就挺好的。将区间一半一半的分开直到分成只有一个点或两个点的时候对于只有两个点的区间最小值就是这两个点的距离只有一个点的区间最小值就是无穷大。注意还要考虑合并的时候可能距离最近的两个点分别在左右两个不同的区间。对于这种情况的处理如下mid(ldrd)/2;ans min(solve(ld, mid), solve(mid1, rd));得到两段区间最小值的最小值 从中间向两边寻找因为我们是按照x坐标排序的在左区间向左边寻找的时候如果某一个点的x到中间点x的距离大于ans否则将这样的点保存那么这个点左边的点就不可能在右区间寻找到相应的点满足两个点的距离小于ans的那么就结束继续查找这样算是一种优化 同理在右区间向右寻找。。。然后对存储的节点按照y坐标进行从小到大的排序。 枚举每两个点寻找最小的距离 1 #includeiostream2 #includecstring 3 #includecstdio4 #includecmath5 #includealgorithm6 #define MAX 99999999999999.07 using namespace std;8 9 struct node{
10 double x, y;
11 }nd[100005], ndx[100005];
12
13 bool cmp(node a, node b){
14 if(a.x b.x) return a.y b.y;
15 return a.x b.x;
16 }
17
18 bool cmpy(node a, node b){
19 return a.y b.y;
20 }
21
22 double dist(node a, node b){
23 return sqrt((a.x-b.x)*(a.x-b.x) (a.y-b.y)*(a.y-b.y));
24 }
25
26 double solve(int ld, int rd){
27 if(ld rd) return MAX;
28 if(ld 1 rd) return dist(nd[ld], nd[rd]);
29 int mid (ldrd)/2;
30 double ans min(solve(ld, mid), solve(mid1, rd));
31 int len 0;
32 for(int i mid; ild; --i)
33 if(nd[mid].x - nd[i].x ans)
34 ndx[len] nd[i];
35 else break;
36 for(int imid1; ird; i)
37 if(nd[i].x - nd[mid].x ans)
38 ndx[len] nd[i];
39 else break;
40
41 sort(ndx, ndxlen, cmpy) ;
42 for(int i0; ilen-1; i)
43 for(int ji1; jlen; j)
44 if(ndx[j].y - ndx[i].y ans) break;//这里做一处优化
45 else ans min(ans, dist(ndx[i], ndx[j]));
46 return ans;
47 }
48
49 int main(){
50 int n;
51 while(scanf(%d, n) n){
52 for(int i0; in; i)
53 scanf(%lf%lf, nd[i].x, nd[i].y);
54 sort(nd, ndn, cmp);
55 printf(%.2lf\n, solve(0, n-1)/2.0);
56 }
57 return 0;
58 } 转载于:https://www.cnblogs.com/hujunzheng/p/4348418.html
