时间复杂度：O(n㏒n) 思路：Graham扫描的思想和Jarris步进法类似，也是先找到凸包上的一个点，然后从那个点开始按逆时针方向逐个找凸包上的点，但它不是利用夹角。 步骤：
把所有点放在二维坐标系中，则纵坐标最小的点一定是凸包上的点，如图中的P0。把所有点的坐标平移一下，使 P0 作为原点，如上图。计算各个点相对于 P0 的幅角 α ，按从小到大的顺序对各个点排序。当 α 相同时，距离 P0 比较近的排在前面。例如上图得到的结果为 P1，P2，P3，P4，P5，P6，P7，P8。我们由几何知识可以知道，结果中第一个点 P1 和最后一个点 P8 一定是凸包上的点。 （以上是准备步骤，以下开始求凸包） 以上，我们已经知道了凸包上的第一个点 P0 和第二个点 P1，我们把它们放在栈里面。现在从步骤3求得的那个结果里，把 P1 后面的那个点拿出来做当前点，即 P2 。接下来开始找第三个点：连接P0和栈顶的那个点，得到直线 L 。看当前点是在直线 L 的右边还是左边。如果在直线的右边就执行步骤5；如果在直线上，或者在直线的左边就执行步骤6。如果在右边，则栈顶的那个元素不是凸包上的点，把栈顶元素出栈。执行步骤4。当前点是凸包上的点，把它压入栈，执行步骤7。检查当前的点 P2 是不是步骤3那个结果的最后一个元素。是最后一个元素的话就结束。如果不是的话就把 P2 后面那个点做当前点，返回步骤4。最后，栈中的元素就是凸包上的点了。 以下为用Graham扫描法动态求解的过程：
算法思想转载自：http://blog.csdn.net/bone_ace/article/details/46239187 #include<bits/stdc++.h> using namespace std; const int maxn = 1000 + 10; #define INF 0x3f3f3f3f #define eps 10e-8 int n,m; struct Node { double x,y; double coss; }; Node a[maxn]; Node s; double ccoss(Node t) { return (t.x - s.x) / sqrt((t.x - s.x) * (t.x - s.x) + (t.y - s.y) *(t.y - s.y)); } double distances(Node p1,Node p2) { return sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y)); } void Input() { s.x = INF; s.y = INF; for(int i = 1; i <= n; i ++) { scanf("%lf%lf",&a[i].x,&a[i].y); if((a[i].y < s.y) || (s.y == a[i].y && s.x > a[i].x) ) s = a[i]; } } double across(Node p1,Node p2,Node p3) { return (p1.x - p2.x) * (p3.y - p2.y) - (p1.y - p2.y) * (p3.x - p2.x); } bool cmp(Node aa,Node bb) { if(fabs(aa.coss - bb.coss) < eps) return fabs(aa.x - s.x) < fabs(bb.x - s.x); return aa.coss > bb.coss; } void sorts() { for(int i = 1; i <= n; i ++) { if(a[i].x == s.x && a[i].y == s.y) { a[i].coss = 1.0; } else a[i].coss = ccoss(a[i]); } sort(a+1,a+n+1,cmp); } void graham() { Node st[maxn]; int len = 0; st[len ++] = a[1]; if(n>= 2) st[len ++] = a[2]; if(n >= 3) st[len ++] = a[3]; for(int i = 3; i <= n; i ++) { while(across(st[len - 1],st[len - 2],a[i]) <= 0) { len --; } st[len ++] = a[i]; } // for(int i = 0; i < len; i ++) // cout << st[i].x << " " <<st[i].y <<endl; double ans = 0; for(int i = 0; i < len - 1; i ++) { ans += distances(st[i],st[i + 1]); } ans += distances(st[0],st[len - 1]) ; printf("%.2lf\n",ans); } void solve() { sorts(); graham(); } int main() { while( ~ scanf("%d",&n) && n) { Input(); solve(); } return 0; }