所需基础
计算几何 - 凸包、了解 Graham's Scan 算法及其极角序实现。
概述
Graham's Scan 算法的水平序实现是不同于「极角序」的另一种实现方式,它将平面点集按照水平序排序,即按 y 坐标排序,相同时再按 x 坐标排序,之后进行扫描来求得凸包。
优势
- 排序规则更简单
- 起始点十分容易确定
- 解决了「极角序」方法中的共线点问题
时间复杂度
$O(nlogn)$
算法实现
- 将平面点集按照先 y 后 x 升序排序(图例中存在刻意设定的共线点情况);
- 做右链扫描 (下标 0 ~ n-1);
- 反向做左链扫描(下标 n-1 ~ 0),忽略右链扫描时已生成的点。此部分图例用红线标出。
代码实现
const int MAXN = ?; // n 的最大值
struct point {
int x;
int y;
point operator - (const point &p) const {
point ret;
ret.x = x - p.x;
ret.y = y - p.y;
return ret;
}
} p[MAXN]; // 点集数组
int n; // 点的个数
// 水平序的排序比较函数
bool cmp(point a, point b) {
if(a.y != b.y) return a.y < b.y;
else return a.x < b.x;
}
// Det 和 Cross 函数用于计算叉积
int Det(int x1, int y1, int x2, int y2) {
return x1*y2 - x2*y1;
}
int Cross(point a, point b, point p) {
return Det(b.x-a.x, b.y-a.y, p.x-a.x, p.y-a.y);
}
// 计算平面上两点间直线距离
int CalculateDistance(point a, point b) {
point p = a - b;
return p.x*p.x + p.y*p.y;
}
// Graham's Scan 算法(水平序)
void GrahamScan() {
sort(p, p+n, cmp); // 水平序排序
point res[MAXN]; // 用来记录求得的凸包点集
int top = 0;
for(int i=0; i<n; ++i) { // 反向扫描右链
while(top>=2 && Cross(res[top-2], res[top-1], p[i])<0) {
top--;
}
res[top++] = p[i];
}
int tmp = top;
for(int i=n-2; i>=0; --i) { // 扫描左链
// "top>tmp" 用于保证右链已生成的点不会被左链扫描所影响
while(top>tmp && Cross(res[top-2], res[top-1], p[i])<0) {
top--;
}
res[top++] = p[i];
}
}
例题讲解
大致题意
给出二维平面中的一组点集,求最大的两点间距离的平方。
解题思路
首先求得所给点集的凸包,然后枚举凸包上的所有点对,找出其中最大的两点间距离即可。
参考代码
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
const int MAXN = 50000;
struct point {
int x;
int y;
point operator - (const point &p) const {
point ret;
ret.x = x - p.x;
ret.y = y - p.y;
return ret;
}
} p[MAXN];
int n;
bool cmp(point a, point b) {
if(a.y != b.y) return a.y < b.y;
else return a.x < b.x;
}
int Det(int x1, int y1, int x2, int y2) {
return x1*y2 - x2*y1;
}
int Cross(point a, point b, point p) {
return Det(b.x-a.x, b.y-a.y, p.x-a.x, p.y-a.y);
}
int CalculateDistance(point a, point b) {
point p = a - b;
return p.x*p.x + p.y*p.y;
}
int GrahamScan() {
sort(p, p+n, cmp);
point res[MAXN];
int top = 0;
for(int i=0; i<n; ++i) {
while(top>=2 && Cross(res[top-2], res[top-1], p[i])<0) {
top--;
}
res[top++] = p[i];
}
int tmp = top;
for(int i=n-2; i>=0; --i) {
while(top>tmp && Cross(res[top-2], res[top-1], p[i])<0) {
top--;
}
res[top++] = p[i];
}
int ans = 0;
// 枚举凸包上的所有点对
for(int i=0; i<top-2; ++i) {
for(int j=i+1; j<top-1; ++j) {
ans = max(ans, CalculateDistance(res[i], res[j]));
}
}
return ans;
}
int main(int argc, char const *argv[]) {
scanf("%d", &n);
for(int i=0; i<n; ++i) {
scanf("%d %d", &p[i].x, &p[i].y);
}
printf("%d\n", GrahamScan());
return 0;
}
参考资料
- 《算法艺术与信息学竞赛》(清华大学出版社) 刘汝佳 黄亮 著
还不快抢沙发