对于初学计算几何的OIer来说，Graham算法是个不错的凸包算法。Graham算法相比极角排序法来说，更为直观也更容易理解。
数据定义
class Point {
public:
double x, y;
Point(double x = 0, double y = 0):x(x), y(y) {}
Point(Point a, Point b) {
//构造从a到b的向量
x = b.x - a.x;
y = b.y - a.y;
}
double dist(const Point& p) const {
//计算从自身到点P的距离
return sqrt((x - p.x) * (x - p.x) + (y - p.y) * (y - p.y));
}
double operator * (const Point& p) const {
//计算向量叉积
return x * p.y - p.x * y;
}
bool operator < (const Point& p) const {
//按照X轴排序
return (x == p.x) ? (y < p.y) : (x < p.x);
}
friend istream& operator >> (istream& in, Point& p) {
//重载 >> 运算符使得cin可以输入
in >> p.x >> p.y;
return in;
}
};
const int MAXN = 10000 + 5;
Point p[MAXN];
int st[MAXN], top = -1; //点栈
int n;
主程序
void input() { //输入所有点
cin >> n;
for(int i = 0; i < n; i++) {
cin >> p[i];
}
}
int main() {
input();
sort(p, p + n); //对点进行直角坐标排序??????
double ans = 0;
st[++top] = 0; //将第一个点入栈
st[++top] = 1; //将第二个点入栈
for(int i = 2; i < n; i++) {
Point u(p[st[top - 1]], p[st[top]]); //计算栈顶两个点构成的向量
Point v(p[st[top]], p[i]); //计算当前点与栈顶构成的向量
while(u * v < 0) { //若叉积小于0
if(top == 0) { //当栈中只有一个元素时，退出循环
break;
}
top--; //弹出栈顶
u = Point(p[st[top - 1]], p[st[top]]); //更新
v = Point(p[st[top]], p[i]); //更新
}
st[++top] = i; //将第i个点压入栈中
}
for(int i = 0; i <= top - 1; i++) {
ans += p[st[i]].dist(p[st[i + 1]]); //累加下半个凸包的长度
}
top = -1; //清空栈
//求出上半个凸包，与前半部分大同小异
st[++top] = 0;
st[++top] = 1;
for(int i = 2; i < n; i++) {
Point u(p[st[top - 1]], p[st[top]]);
Point v(p[st[top]], p[i]);
while(u * v > 0) {
if(top == 0) {
break;
}
top--;
u = Point(p[st[top - 1]], p[st[top]]);
v = Point(p[st[top]], p[i]);
}
st[++top] = i;
}
for(int i = 0; i <= top - 1; i++) {
ans += p[st[i]].dist(p[st[i + 1]]);
}
top = -1;
cout << setprecision(2) << fixed << ans << endl; //控制精度
return 0;
}
转载于:https://www.cnblogs.com/Helium-Air/p/convex-hull.html
相关资源：计算几何求凸包（安德鲁算法）
