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++ ,
