最远点对问题 » NoAlGo博客
二维平面上有n个点，怎么寻找距离最远的两个？
凸包（Convex Hull）是一个计算几何的概念，点集Q的凸包是指一个最小凸多边形，满足Q中的点或者在多边形边上或者在其内。直观上来讲，想象n个顶点上各有一枚钉子，使用一根橡皮圈把这所有钉子包围起来得到的图像就是这n个点的凸包。
不难想象，距离最远的点肯定在凸包的顶点上，于是可以先对所有的点求一个凸包，然后再对凸包上的点求最短距离。一般来说，凸包上的点的数量会比原始点的数量少很多，这时我们可以对凸包上的所有进行暴力枚举，所花费的时间不会太大。但对于特殊构造的数据，可能所有的n个点就构成了一个凸包，这时在凸包上枚举跟直接在原始点集上枚举是一样的，复杂度仍然为O(n^2)，这时我们可以选择使用旋转卡壳方法求取最远点对。
旋转卡壳算法
struct Point
{
double x, y;
Point (double a = 0, double b = 0): x(a), y(b) {}
} v[mxsz]; //顶点集
int stk[mxsz], top; //graham扫描得到的凸包顶点下标
//计算欧几里得距离
inline double calDis(const Point &p1, const Point &p2)
{
return sqrt((p1.x-p2.x)*(p1.x-p2.x) + (p1.y-p2.y)*(p1.y-p2.y));
}
//计算向量ab和向量cd的叉乘
double cross(const Point &a, const Point &b, const Point &c, const Point &d)
{
double x1 = b.x - a.x, y1 = b.y - a.y, x2 = d.x - c.x, y2 = d.y - c.y;
return x1 * y2 - x2 * y1;
}
bool cmp(const Point &a, const Point &b)
{
double t = cross(v[0], a, v[0], b);
if (fabs(t) < 1e-6) return calDis(v[0], a) < calDis(v[0], b);
else return t > 0; //右手法则，叉乘为正，则由a到b为逆时针
}
//graham扫描法求凸包
void graham (int n)
{
//最左下角的点放到首位
int id = 0;
for (int i = 1; i < n; i++)
if (v[i].y < v[id].y || (v[i].y == v[id].y && v[i].x < v[id].x))
id = i;
swap(v[0], v[id]);
//极角排序
sort(v+1, v+n, cmp);
//前两个点直接入栈
for (int i = 0; i <= 1; i++) stk[i] = i;
top = 1;
for (int i = 2; i < n; i++)
{
while (top > 0 && cross(v[stk[top-1]], v[stk[top]], v[stk[top-1]], v[i]) <= 0)
top--; //共线的点只保留两端，如果n个点均共线，则最终只得到首尾两个端点
stk[++top] = i;
}
}
//旋转卡壳求凸包的直径
double rorating_caliper()
{
double ans = 0;
stk[++top] = 0; //最后一个点即为最开始的点
for (int i = 0, j = 2; i < top; i++)
{
while (cross(v[stk[i]], v[stk[i+1]], v[stk[i]], v[stk[j]])
< cross(v[stk[i]], v[stk[i+1]], v[stk[i]], v[stk[j+1]]))
j = (j + 1) % top;
ans = max(ans, max(calDis(v[stk[i]], v[stk[j]]), calDis(v[stk[i+1]], v[stk[j]])));
}
return ans;
}
int main()
{
//输入n个点
int n; scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%lf%lf", &v[i].x, &v[i].y);
//graham扫描法求凸包
graham(n);
//旋转卡壳求最远距离
double len = rorating_caliper();
printf("Longest distance is: %lf\n", len);
}
Read full article from
最远点对问题 » NoAlGo博客
