首页 / 算法 / 平面凸包Graham算法
平面凸包Graham算法
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了平面凸包Graham算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2223字，纯文字阅读大概需要4分钟。
内容图文
平面凸包问题是计算几何中的一个经典问题
具体就是给出平面上的多个点，求一个最小的凸多边形，使得其包含所有的点
具体形象就类似平面上有若干柱子，一个人用绳子从外围将其紧紧缠绕一圈
Graham算法
直接讲算法
我们将所有点排序，分别求出上凸壳和下凸壳，合起来就是凸包
以上凸壳为例子，我们先将最左边的点加入凸包【可以想象，最左侧的点一定在凸包上】
之后向后查找：
1、若当前凸包内只有一点，那么加入新的点
2、如果当前凸包内不止一个点，检验新加入的点与凸包最后一个点所在直线与当前凸包最后两点坐在直线的关系
如果是这样：
满足上凸性，加入凸包
但是如果是这样：
不满足上凸性，就不加入
具体判断可以用斜率也可以用叉乘【我写斜率狂WA，还是叉乘比较滋滋】
扫过一遍，就可以得到上凸壳，下凸壳类似
复杂度\(O(nlogn)\)
hdu1348
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long int
#define REP(i,n) for (int i = 1; i <= (n); i++)
using
namespace std;
constint maxn = 2005,maxm = 100005;
constdouble INF = 1000000000000000000ll;
inlineint read(){
int out = 0,flag = 1; char c = getchar();
while (c < 48 || c > 57) {if (c == ‘-‘) flag = -1; c = getchar();}
while (c >= 48 && c <= 57) {out = (out << 3) + (out << 1) + c - ‘0‘; c = getchar();}
return out * flag;
}
constdouble pi = acos(-1);
struct point{double x,y;}p[maxn];
inlinebooloperator <(const point& a,const point& b){
return a.x == b.x ? a.y < b.y : a.x < b.x;
}
inline point operator -(const point& a,const point& b){
return (point){a.x - b.x,a.y - b.y};
}
inlinedoubleoperator *(const point& a,const point& b){
return a.x * b.y - a.y * b.x;
}
inlinedouble dis(int u,int v){
return sqrt((p[u].x - p[v].x) * (p[u].x - p[v].x) + (p[u].y - p[v].y) * (p[u].y - p[v].y));
}
int T,n,L,q[maxn],tail;
void cal(){
sort(p + 1,p + 1 + n);
q[tail = 1] = 1;
for (int i = 2; i <= n; i++){
while (tail > 1 && (p[i] - p[q[tail]]) * (p[q[tail]] - p[q[tail - 1]]) < 0) tail--;
q[++tail] = i;
}
int last = tail;
for (int i = n - 1; i; i--){
while (tail > last && (p[i] - p[q[tail]]) * (p[q[tail]] - p[q[tail - 1]]) < 0) tail--;
q[++tail] = i;
}
}
void print(){
double ans = 0;
for (int i = 1; i < tail; i++) ans += dis(q[i],q[i + 1]);
ans += 2.0 * pi * L;
if (T) printf("%.0lf\n\n",ans);
else printf("%.0lf\n",ans);
}
int main(){
T = read();
while (T--){
n = read(); L = read();
for (int i = 1; i <= n; i++) p[i].x = read(),p[i].y = read();
cal();
print();
}
return0;
}
原文：https://www.cnblogs.com/Mychael/p/8465384.html
内容总结
以上是互联网集市为您收集整理的平面凸包Graham算法全部内容，希望文章能够帮你解决平面凸包Graham算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。