Triangle with no point inside | Python3 program to find 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
import sys NEW_LINE def getDistance ( x1 , y1 , x2 , y2 ) : NEW_LINE INDENT return ( x2 - x1 ) * ( x2 - x1 ) + ( y2 - y1 ) * ( y2 - y1 ) NEW_LINE DEDENT def triangleWithNoPointInside ( points , N ) : NEW_LINE INDENT first = 0 NEW_LINE second = 0 NEW_LINE third = 0 NEW_LINE minD = sys . maxsize NEW_LINE for i in range ( 0 , N ) : NEW_LINE INDENT if i == first : NEW_LINE INDENT continue NEW_LINE DEDENT d = getDistance ( points [ i ] [ 0 ] , points [ i ] [ 1 ] , points [ first ] [ 0 ] , points [ first ] [ 1 ] ) NEW_LINE if minD > d : NEW_LINE INDENT minD = d NEW_LINE second = i NEW_LINE DEDENT DEDENT minD = sys . maxsize NEW_LINE for i in range ( 0 , N ) : NEW_LINE INDENT if i == first or i == second : NEW_LINE INDENT continue NEW_LINE DEDENT d = getDistance ( points [ i ] [ 0 ] , points [ i ] [ 1 ] , points [ first ] [ 0 ] , points [ first ] [ 1 ] ) NEW_LINE 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 ] ) and minD > d ) : NEW_LINE INDENT minD = d NEW_LINE third = i NEW_LINE DEDENT DEDENT print ( points [ first ] [ 0 ] , ' , ▁ ' , points [ first ] [ 1 ] ) NEW_LINE print ( points [ second ] [ 0 ] , ' , ▁ ' , points [ second ] [ 1 ] ) NEW_LINE print ( points [ third ] [ 0 ] , ' , ▁ ' , points [ third ] [ 1 ] ) NEW_LINE DEDENT points = [ [ 0 , 0 ] , [ 0 , 2 ] , [ 2 , 0 ] , [ 2 , 2 ] , [ 1 , 1 ] ] NEW_LINE N = len ( points ) NEW_LINE triangleWithNoPointInside ( points , N ) NEW_LINE