checks whether the point crosses the convex hull or not
int orientation ( pair < int , int > a , pair < int , int > b , pair < int , int > c ) { int res = ( b . second - a . second ) * ( c . first - b . first ) - ( c . second - b . second ) * ( b . first - a . first ) ; if ( res == 0 ) return 0 ; if ( res > 0 ) return 1 ; return -1 ; }