Triangle with no point inside | method to get square of distance between ( x1 , y1 ) and ( x2 , y2 ) ; Method prints points which make triangle with no point inside ; any point can be chosen as first point of triangle ; choose nearest point as second point of triangle ; Get distance from first point and choose nearest one ; Pick third point by finding the second closest point with different slope . ; if already chosen point then skip them ; get distance from first point ; here cross multiplication is compared instead of division comparison ; Driver code
function getDistance ( x1 , y1 , x2 , y2 ) { return ( x2 - x1 ) * ( x2 - x1 ) + ( y2 - y1 ) * ( y2 - y1 ) ; } function triangleWithNoPointInside ( points , N ) { var first = 0 ; var second = 0 ; var third = 0 ; var minD = Number . MAX_VALUE ; for ( i = 0 ; i < N ; i ++ ) { if ( i == first ) continue ; var d = getDistance ( points [ i ] [ 0 ] , points [ i ] [ 1 ] , points [ first ] [ 0 ] , points [ first ] [ 1 ] ) ; if ( minD > d ) { minD = d ; second = i ; } } minD = Number . MAX_VALUE ; for ( i = 0 ; i < N ; i ++ ) { if ( i == first i == second ) continue ; var d = getDistance ( points [ i ] [ 0 ] , points [ i ] [ 1 ] , points [ first ] [ 0 ] , points [ first ] [ 1 ] ) ; if ( ( points [ i ] [ 0 ] - points [ first ] [ 0 ] ) * ( points [ second ] [ 1 ] - points [ first ] [ 1 ] ) != ( points [ second ] [ 0 ] - points [ first ] [ 0 ] ) * ( points [ i ] [ 1 ] - points [ first ] [ 1 ] ) && minD > d ) { minD = d ; third = i ; } } document . write ( points [ first ] [ 0 ] + " " + points [ first ] [ 1 ] + " " ) ; document . write ( points [ second ] [ 0 ] + " " + points [ second ] [ 1 ] + " " ) ; document . write ( points [ third ] [ 0 ] + " " + points [ third ] [ 1 ] + " " ) ; } var points = [ [ 0 , 0 ] , [ 0 , 2 ] , [ 2 , 0 ] , [ 2 , 2 ] , [ 1 , 1 ] ] ; var N = points . length ; triangleWithNoPointInside ( points , N ) ;