网络建站东北,江门网站建设方案开发,idea网站开发,zencart网站打不开之前看过#xff0c;可是当时没有细看#xff0c;今天在网上搜了一下#xff0c;看了一下别人的思路#xff0c;毕竟这也是一类问题的经典。过一段时间再将自己对其认识总结。现在先转载别人的思路。 出处#xff1a;http://blog.csdn.net/sd6264456/article/details/9318… 之前看过可是当时没有细看今天在网上搜了一下看了一下别人的思路毕竟这也是一类问题的经典。过一段时间再将自己对其认识总结。现在先转载别人的思路。 出处http://blog.csdn.net/sd6264456/article/details/9318861 给n个点的坐标求距离最近的一对点之间距离的一半。第一行是一个数n表示有n个点接下来n行是n个点的x坐标和y坐标实数。 这个题目其实就是求最近点对的距离。主要思想就是分治。先把n个点按x坐标排序然后求左边n/2个和右边n/2个的最近距离最后合并。合并要重点说一下比较麻烦。 首先假设点是n个编号为1到n。我们要分治求则找一个中间的编号mid先求出1到mid点的最近距离设为d1还有mid1到n的最近距离设为 d2。这里的点需要按x坐标的顺序排好并且假设这些点中没有2点在同一个位置。若有则直接最小距离为0了。 然后令d为d1, d2中较小的那个点。如果说最近点对中的两点都在1-mid集合中或者mid1到n集合中则d就是最小距离了。但是还有可能的是最近点对中的两点分 属这两个集合所以我们必须先检测一下这种情况是否会存在若存在则把这个最近点对的距离记录下来去更新d。这样我们就可以得道最小的距离d了。 关键是要去检测最近点对理论上每个点都要和对面集合的点匹配一次那效率还是不能满足我们的要求。所以这里要优化。怎么优化呢考虑一下假如以我们所 选的分割点mid为界如果某一点的横坐标到点mid的横坐标的绝对值超过d1并且超过d2那么这个点到mid点的距离必然超过d1和d2中的小者所 以这个点到对方集合的任意点的距离必然不是所有点中最小的。 所以我们先把在mid为界左右一个范围内的点全部筛选出来放到一个集合里。筛选好以后当然可以把这些点两两求距离去更新d了不过这样还是很慢万一 满足条件的点很多呢。这里还得继续优化。首先把这些点按y坐标排序。假设排序好以后有cnt个点编号为0到cnt-1。那么我们用0号去和1到cnt- 1号的点求一下距离然后1号和2到cnt-1号的点求一下距离。。。如果某两个点y轴距离已经超过了d这次循环就可以直接break了开始从下一个 点查找了. 1 #include cmath2 #include algorithm3 #include iostream4 #include string.h5 using namespace std;6 struct node7 {8 double x,y;9 }a[100005];
10 int c[100005];
11 double cmpy(int t1,int t2)
12 {
13 return a[t1].ya[t2].y;
14 }
15 bool cmp(node t1,node t2)
16 {
17 return t1.xt2.x;
18 }
19 double dis(node t1,node t2)
20 {
21 return sqrt((t1.x-t2.x)*(t1.x-t2.x)(t1.y-t2.y)*(t1.y-t2.y));
22 }
23 double min(double t1,double t2)
24 {
25 return t1t2?t1:t2;
26 }
27 double find(int left,int right)
28 {
29 if(left1right)
30 return dis(a[left],a[right]);
31 if(left2right)
32 return min(dis(a[left],a[right]),min(dis(a[left],a[left1]),dis(a[left1],a[right])));
33 int mid(leftright)1;
34 double ansmin(find(left,mid),find(mid1,right));
35 int i,j,cnt0;
36 for(ileft;iright;i)
37 {
38 if(a[i].xa[mid].x-ansa[i].xa[mid].xans)
39 c[cnt]i;
40 }
41 sort(c,ccnt,cmpy);
42 for(i0;icnt;i)
43 {
44 for(ji1;jcnt;j)
45 {
46 if(a[c[j]].y-a[c[i]].yans)
47 break;
48 ansmin(ans,dis(a[c[i]],a[c[j]]));
49 }
50 }
51 return ans;
52
53 }
54 int main()
55 {
56 int n,i;
57 while(cinn,n)
58 {
59 for(i0;in;i)
60 {
61 cina[i].xa[i].y;
62 }
63 std::sort(a,an,cmp);
64 printf(%.2lf\n,find(0,n-1)/2);
65 }
66 return 0;
67 } 转载于:https://www.cnblogs.com/sineatos/p/3229107.html
