UVa 11626 - Convex Hull


		题目：按逆时针顺序输出凸包上的点，左下角为起点。
 
分析：计算几何、凸包。题目会给出是够是凸包上的点，不在凸包上的可以忽略。
 
注意：共线点的处理，如果用int叉乘会溢出。
 
[cpp]  
#include <algorithm>   
#include <iostream>  
#include <cstdlib>  
#include <cstdio>  
#include <cmath>  
  
using namespace std;  
  
typedef struct pnode  
{  
    double x,y,d;  
}point;   
point P[ 100001 ];  
point S[ 100001 ];  
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;  
}  
  
void 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];  
        }  
    }  
      
    printf("%d\n",top+1);  
    for ( int i = 0 ; i <= top ; ++ i )  
        printf("%.0lf %.0lf\n",S[i].x,S[i].y);  
}  
  
int main()  
{  
    int  N,T;   
    char C;  
    while ( scanf("%d",&T) != EOF )   
    while ( T -- ) {  
        scanf("%d",&N);  
        int count = 0;  
        for ( int i = 0 ; i < N ; ++ i ) {  
            scanf("%lf %lf %c",&P[count].x,&P[count].y,&C);  
            if ( C == 'Y' ) count ++;  
        }  
          
        Graham( count );  
    }  
    return 0;  
}

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