題目：按逆時針順序輸出凸包上的點，左下角為起點。 分析：計算幾何、凸包。題目會給出是夠是凸包上的點，不在凸包上的可以忽略。 注意：共線點的處理，如果用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; }
