计算几何相关笔记

几何相关笔记"/>

计算几何相关笔记

距离

欧拉距离

就是我们最熟悉的两点之间距离公式： 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);
}

然后我们就可以考虑分治了。我们用一条线不断分割区间，显然对于要求的“最近点对”，一共由三种情况：

1. 在左区间内

2. 在右区间内

3. 横跨左右区间

对于前面的两种情况，我们可以用分治操作来递归解决。我们假设在左区间和右区间里求得的点对举例最小值 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 maxn=4*1e5+5;struct node
{long long x,y;
}dot[maxn];long long q[maxn];inline bool cmp(int a,int b)
{return dot[a].y<dot[b].y;
}inline bool cmpp(node a, node b) 
{return a.x<b.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(l==r) return 1ll<<62;if(l==r-1) return dis(l,r);long long mid=(l+r)>>1;long long d;d=min(work(l,mid),work(mid+1,r));int tot=0;//记录q集合中的总点数for(int i=l;i<=r;i++)if(1ll*(dot[mid].x-dot[i].x)*(dot[mid].x-dot[i].x)<d) q[++tot]=i;//q存储编号sort(q+1,q+tot+1,cmp);for(int i=1;i<=tot;i++)for(int j=i+1;j<=tot&&1ll*(dot[q[i]].y-dot[q[j]].y)*(dot[q[i]].y-dot[q[j]].y)<d;j++)d=min(d,dis(q[i],q[j]));return d;
}signed main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);long long n;cin>>n;for(long long i=1;i<=n;i++) cin>>dot[i].x>>dot[i].y;sort(dot+1,dot+n+1,cmpp);cout<<work(1,n);return 0;
}

加强版 | 加强加强版