题目大意：求凸包边缘的长度
解题思路：标准的凸包Graham算法
#include < iostream > #include < cmath > #define PI acos(-1.0) const double eps = 1e - 6 ; int sgn( double a) { return (a > eps) - (a <- eps);} struct point{ double x,y; point ( double xx = 0 , double yy = 0 ){ // 构造函数 x = xx; y = yy; } point operator - (point b){ return point(x - b.x,y - b.y); } double operator * (point b){ return (x * b.y - y * b.x); } double len(){ return sqrt(x * x + y * y); } void input(){ scanf( " %lf%lf " , & x, & y); }}p[ 102 ]; int stack[ 102 ],top; int cmp( const void * a, const void * b) // 逆时针排序 返回正数要交换 { struct point * c = ( struct point * )a; struct point * d = ( struct point * )b; double k = ( * c - p[ 0 ]) * ( * d - p[ 0 ]); if (sgn(k) < 0 ) return 1 ; else if (sgn(k) == 0 && sgn(( * c - p[ 0 ]).len() - ( * d - p[ 0 ]).len()) >= 0 ) return 1 ; else return - 1 ;} void graham( int n) // 形成凸包 { int i; for (i = 0 ;i <= 2 ;i ++ ) stack[i] = i; top = 2 ; for (i = 3 ;i < n;i ++ ) { while ( sgn((p[i] - p[stack[top - 1 ]]) * (p[stack[top]] - p[stack[top - 1 ]])) > 0 ){ top -- ; if (top == 0 ) break ; } top ++ ; stack[top] = i; }} int main(){ int n,i; double sum; while (scanf( " %d " , & n),n) { for (i = 0 ;i < n;i ++ ) p[i].input(); if (n == 1 ){ printf( " 0.00\n " ); continue ; } if (n == 2 ){ printf( " %.2lf\n " ,(p[ 0 ] - p[ 1 ]).len()); continue ; } int u = 0 ; for (i = 1 ;i < n;i ++ ) // 找左下角的点 if (p[i].y < p[u].y || (p[i].y == p[u].y && p[i].x < p[u].x) ) u = i; // swap point tmp = p[ 0 ]; p[ 0 ] = p[u]; p[u] = tmp; qsort(p + 1 ,n - 1 , sizeof (p[ 0 ]),cmp); graham(n); sum = 0 ; for (i = 0 ;i <= top;i ++ ) sum += (p[stack[i]] - p[stack[(i + 1 ) % (top + 1 )]]).len(); printf( " %.2lf\n " ,sum); } return 0 ;}PS;这题和ZJU1453、FOJ1333一样，但ZJU和FOJ上n==2时输出2*(p[0]-p[1]).len()。
转载于:https://www.cnblogs.com/DreamUp/archive/2010/08/29/1811829.html
相关资源：JAVA上百实例源码以及开源项目