iframe 网站前台模板,中国建筑官网测评,企业年金的好处和坏处,江苏嘉力电力建设有限公司网站距离
欧拉距离
就是我们最熟悉的两点之间距离公式#xff1a; d ( x 1 − x 2 ) 2 ( y 1 − y 2 ) 2 d\sqrt{(x_1-x_2)^2(y_1-y_2)^2} d(x1−x2)2(y1−y2)2
曼哈顿距离
相对于欧拉距离#xff0c;曼哈顿距离的计算更加简单#xff0c;并且没有开方过程 d ( x 1 − x 2 ) 2 ( y 1 − y 2 ) 2 d\sqrt{(x_1-x_2)^2(y_1-y_2)^2} d(x1−x2)2(y1−y2)2
曼哈顿距离
相对于欧拉距离曼哈顿距离的计算更加简单并且没有开方过程在计算机的运行过程中误差更小。
公式 d ∣ x 1 − x 2 ∣ ∣ y 1 − y 2 ∣ d|x_1-x_2||y_1-y_2| d∣x1−x2∣∣y1−y2∣。
关于曼哈顿距离有一些有趣的故事 QwQ 曼哈顿距离的发明者是 19 19 19 世纪著名的德国犹太人数学家赫尔曼·闵可夫斯基他也是爱因斯坦的老师、四维时空理论的创始人。曼哈顿距离又叫出租车距离主要是由于在纽约曼哈顿这也是它为什么叫曼哈顿距离计算出租车的距离时经常用街区表示而经过几个街区就是曼哈顿距离的数值。 平面最近点对 给定 n n n 个二维欧几里得平面上的点 p 1 , p 2 , … , p n p_1, p_2, \dots, p_n p1,p2,…,pn请输出距离最近的两个点的距离。 我们按照 x x x 的值即横坐标进行分治其实就是一个不断二分区间的过程。利用 y y y 的值即纵坐标进行归并排序。
为了方便起见我们首先可以定义一个函数专门用来求两点之间的欧拉距离
int dis(int a,int b)//计算两点间距离
{return (a.x-b.x)*(a.x-b.x)(a.y-b.y)*(a.y-b.y);
}然后我们就可以考虑分治了。我们用一条线不断分割区间显然对于要求的“最近点对”一共由三种情况 在左区间内 在右区间内 横跨左右区间
对于前面的两种情况我们可以用分治操作来递归解决。我们假设在左区间和右区间里求得的点对举例最小值 d d d 那么对于满足情况 3 3 3 的跨区间点对我们在左右区间靠近中分线的的位置各画一条举例中分线为 d d d 的线可知最近点对一定在这两条线之间。证明很简单因为只有这样才有可能替换掉当前最小的 d d d。
我们可以开一个新的数组 q 来存储这两条线之间的点。把区间按照纵轴方向分成宽度为 d d d 的几组。为什么要这样分可以考虑对于这个区间内的任意一个点为了满足点对距离最短我们以 d d d 为半径画圆最近点对一定在这个圆内所以我们按照 d d d 纵向分割之后对一个点我们只需要考虑与它相邻的、在它上方的、下方的 d × d d\times d d×d 方块中的点。又由于可以证明每个方块中至多有 2 2 2 个点于是乎我们最多只需要枚举 6 6 6 个点时间复杂度达标。
总时间复杂度为 O ( n log n ) O(n\log n) O(nlogn)代码如下
#include bits/stdc.h
using namespace std;const int maxn4*1e55;struct node
{long long x,y;
}dot[maxn];long long q[maxn];inline bool cmp(int a,int b)
{return dot[a].ydot[b].y;
}inline bool cmpp(node a, node b)
{return a.xb.x;
}inline long long dis(int a,int b)//计算两点间距离
{return (long long)(dot[a].x-dot[b].x)*(dot[a].x-dot[b].x)(long long)(dot[a].y-dot[b].y)*(dot[a].y-dot[b].y);
}long long work(int l,int r)
{if(lr) return 1ll62;if(lr-1) return dis(l,r);long long mid(lr)1;long long d;dmin(work(l,mid),work(mid1,r));int tot0;//记录q集合中的总点数for(int il;ir;i)if(1ll*(dot[mid].x-dot[i].x)*(dot[mid].x-dot[i].x)d) q[tot]i;//q存储编号sort(q1,qtot1,cmp);for(int i1;itot;i)for(int ji1;jtot1ll*(dot[q[i]].y-dot[q[j]].y)*(dot[q[i]].y-dot[q[j]].y)d;j)dmin(d,dis(q[i],q[j]));return d;
}signed main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);long long n;cinn;for(long long i1;in;i) cindot[i].xdot[i].y;sort(dot1,dotn1,cmpp);coutwork(1,n);return 0;
}加强版 | 加强加强版
