Posted on 2009-03-17 18:09
杜仲当归 阅读(1350)
评论(0) 编辑 收藏 引用
该死的居然不能重发。。。
int dCmp ( double x )
{
if ( x < -eps )
return -1;
if ( x > eps )
return 1;
return 0;
}
double crossDet ( Point &a, Point &b, Point &c )
{
return dCmp ( ( b.x - a.x ) * ( c.y - a.y ) - ( c.x - a.x ) * ( b.y - a.y ) );
}
void grahamScan ()
{
memset ( used, 0, sizeof ( used ) );
int top;
stack[0] = 0, stack[1] = 1;
top = 1;
int i;
for ( i = 2; i < N; i ++ )
{
if ( crossDet ( p[stack[top - 1]], p[stack[top]], p[i] ) >= 0 )
stack[++ top] = i;
else
{
while ( top > 0 && crossDet ( p[stack[top - 1]], p[stack[top]], p[i] ) < 0 )
top --;
stack[++ top] = i;
}
}
for ( i = 0; i <= top; i ++ )
used[p[stack[i]].id] = 1;
//ps ( top );
for ( i = N - 1; i >= 0; i -- )
{
if ( used[i] )
continue;
if ( crossDet ( p[stack[top - 1]], p[stack[top]], p[i] ) >= 0 )
stack[++ top] = i;
else
{
while ( top > 0 && crossDet ( p[stack[top - 1]], p[stack[top]], p[i] ) < 0 )
top --;
stack[++ top] = i;
}
}
//ps ( top );
}