凸包问题的一个应用，地址：http://acm.pku.edu.cn/JudgeOnline/problem?id=1228
#include < stdio.h >

#include < stdlib.h >

typedef struct
{
    int x;
    int y;
    int addr;
    int flag;
}type;
type p[1005];

int stack[1001];
int top;

int e[1001];
int now;

void inits( )
{

    top = -1;
}

void initf( int n )
{

    now = 1;
    for ( int i=0; i<n; i++ )
    {
        e[i] = 0;
    }
}

void in( int a )
{

    stack[++top] = a;
}

void out()
{

    top --;
}

void f_min( int n )
{

    int i;
    type min;

    min.x = p[0].x;
    min.y = p[0].y;
    min.addr = p[0].addr;
    min.flag = p[0].flag;

    for ( i=1; i<n; i++ )
    {
        if ( min.y > p[i].y )
        {
            min.x = p[i].x;
            min.y = p[i].y;
            min.addr = p[i].addr;
            min.flag = p[i].flag;
        }
        else
        {
            if ( min.y == p[i].y )
            {
                if ( min.x > p[i].x )
                {
                    min.x = p[i].x;
                    min.y = p[i].y;
                    min.addr = p[i].addr;
                    min.flag = p[i].flag;
                }
            }
        }
    }
    p[min.addr].x = p[0].x;
    p[min.addr].y = p[0].y;
    p[min.addr].addr = p[0].addr;
    p[min.addr].flag = p[0].flag;
    p[0].x = min.x;
    p[0].y = min.y;
    p[0].addr = min.addr;
    p[0].flag = min.flag;
}

int mul( type *a, type *b, type *c, type *d )
{

    int x1 = a->x - b->x;
    int y1 = a->y - b->y;
    int x2 = c->x - d->x;
    int y2 = c->y - d->y;

    return x1 * y2 - x2 * y1;
}

int dis( type *a, type *b )
{

    int x = a->x - b->x;
    int y = a->y - b->y;
    return x*x + y*y;
}

int cmp( const void *a, const void *b )
{

    type *c = ( type * )a;
    type *d = ( type * )b;

    int ans = - mul( c, &p[0], d, &p[0] );

    if ( ans==0 )
    {
        if ( dis( c, &p[0] ) > dis( d, &p[0] ) )
        {
            ans = 1;
        }
        else 
        {
            if ( dis( c, &p[0] ) < dis( d, &p[0] ) )
            {
                ans = -1;
            }
        }
    }

    return ans;
}

int aobao( int n )
{

    int i;
    int ans = 1;

    f_min( n );

    qsort( p+1, n-1, sizeof( type ), cmp );

    initf( n+1 );

    inits();
    in( 0 );
    p[0].flag = 1;

    for ( i=1; i<n-1; i++ )
    {    
        if ( mul( &p[i], &p[0], &p[i+1], &p[0] ) != 0 )
        {
            break;
        }
    }
    in( i );
    p[i].flag = 1;

    if ( i == n-1 )
    {
        ans = 0;
        return ans;
    }

    for ( ++i; i<n-1; i++ )
    {
        if ( mul( &p[i], &p[0], &p[i+1], &p[0] ) != 0 )
        {
            break;
        }
    }
    in( i );
    p[i].flag = 1;
        
    for ( ++i; i<n; i++ )
    {
        if ( i < n-1 )
        {
            if ( mul( &p[i], &p[0], &p[i+1], &p[0] ) != 0 )
            {
                if ( mul( &p[i], &p[stack[top-1]], &p[stack[top]], &p[stack[top-1]] ) >= 0 )
                {
                    if ( mul( &p[i], &p[stack[top-1]], &p[stack[top]], &p[stack[top-1]] ) == 0 )
                    {
                        e[now] ++;
                    }
                    p[stack[top]].flag = 0;
                    out();
                }
                else
                {
                    now ++;
                }
                in( i );
                p[i].flag = 1;
            }
        }
        else
        {
            if ( mul( &p[i], &p[stack[top-1]], &p[stack[top]], &p[stack[top-1]] ) >= 0 )
            {
                if ( mul( &p[i], &p[stack[top-1]], &p[stack[top]], &p[stack[top-1]] ) == 0 )
                {
                    e[now] ++;
                }
                p[stack[top]].flag = 0;
                out();
            }
            else
            {
                now ++;
            }
        }
    }

    in( n-1 );
    p[n-1].flag = 1;
    now ++;

    return ans;
}

int main()
{

    int n, t;
    int i;
    int ans;
    scanf( "%d", &t );
    
    while ( t-- )
    {
        scanf( "%d", &n );
        for ( i=0; i<n; i++ )
        {
            scanf( "%d%d", &p[i].x, &p[i]. y );
            p[i].addr = i;
            p[i].flag = 0;
        }

        if ( n < 3 )
        {
            printf( "NO\n" );
            continue;
        }

        if ( !aobao( n ) )
        {
            printf( "NO\n" );
            continue;
        }

        for ( i=1; i<n-1; i++ )
        {    
            if ( mul( &p[i], &p[0], &p[i+1], &p[0] ) != 0 )
            {
                break;
            }
        }
        if ( i > 1 )
        {
            e[0] = i;
        }

        for ( i=n-2; i>0; i-- )
        {
            if ( mul( &p[i], &p[0], &p[i+1], &p[0] ) != 0 )
            {
                break;
            }
        }
        if ( n-i > 2 )
        {
            e[now] = n-i;
        }

        ans = 1;
        for( i=0; i<=now; i++ )
        {
            ans *= e[i]; 
        }

        if( ans )
        {
            printf( "YES\n" );
        }
        else
        {
            printf( "NO\n" );
        }
    }

    return 0;
}