UVa 218 - Moth Eradication

		题目：求凸包上的点和凸包周长。
 
分析：计算几何、凸包。直接利用graham算法求解即可，按顺时针方向求解，注意叉乘符号。
 
注意：点小于3个的情况、不过我的凸包算法对n>0都可以求解、而且是所有的点。
 
[cpp] 
#include <algorithm>   
#include <iostream>  
#include <cstdlib>  
#include <cstdio>  
#include <cmath>  
  
using namespace std;  
  
typedef struct pnode  
{  
    double x,y,d;  
}point;   
point P[ 10000 ];  
point S[ 10000 ];  
point MP;  
  
double crossproduct( point a, point b, point c )//ab到ac   
{  
    return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);  
}  
  
double dist( point a, point b )  
{  
    return sqrt((b.x-a.x)*(b.x-a.x)+(b.y-a.y)*(b.y-a.y));  
}  
  
bool cmp1( point a, point b )  
{  
    if ( a.x == b.x ) return a.y < b.y;  
    else return a.x < b.x;  
}  
  
bool cmp2( point a, point b )  
{  
    return crossproduct( P[0], a, b ) < 0;  
}  
  
bool cmp3( point a, point b )  
{  
    double cp = crossproduct( P[0], a, b );  
    if ( cp == 0.0 ) {  
        if ( !crossproduct( P[0], a, MP ) )//在回边上   
            return a.d > b.d;  
        else return a.d < b.d;  
    }else return cp < 0;  
}  
  
double Graham( int N )  
{  
    sort( P+0, P+N, cmp1 );  
    sort( P+1, P+N, cmp2 );  
    //处理共线   
    for ( int i = 1 ; i < N ; ++ i )  
        P[i].d = dist( P[0], P[i] );  
    MP = P[N-1];  
    sort( P+1, P+N, cmp3 );  
      
    int top = -1;  
    if ( N > 0 ) S[++ top] = P[0];  
    if ( N > 1 ) S[++ top] = P[1];  
    if ( N > 2 ) {  
        S[++ top] = P[2];  
        for ( int i = 3 ; i < N ; ++ i ) {  
            while ( crossproduct( S[top-1], S[top], P[i] ) > 0 ) -- top;  
            S[++ top] = P[i];  
        }  
    }  
    S[++ top] = P[0];  
      
    double L = 0.0;  
    for ( int i = 0 ; i < top ; ++ i ) {  
        L += dist( S[i], S[i+1] );  
        printf("(%.1lf,%.1lf)-",S[i].x,S[i].y);  
    }printf("(%.1lf,%.1lf)\n",S[0].x,S[0].y);  
    printf("Perimeter length = %.2lf\n",L);  
      
    return L;  
}  
  
int main()  
{  
    int N,T = 1;   
    while ( scanf("%d",&N) && N ) {  
        for ( int i = 0 ; i < N ; ++ i )  
            scanf("%lf%lf",&P[i].x,&P[i].y);  
          
        if ( T > 1 ) printf("\n");  
        printf("Region #%d:\n",T ++);  
        Graham( N );  
    }  
    return 0;  
}  
 
						
		
	

补充：软件开发 , C++ ,

上一个：UVa 11626 - Convex Hull
下一个：C++ 声明和初始化辨析