Triangle with no point inside | Java 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 java . io . * ; class GFG { static int getDistance ( int x1 , int y1 , int x2 , int y2 ) { return ( x2 - x1 ) * ( x2 - x1 ) + ( y2 - y1 ) * ( y2 - y1 ) ; } static void triangleWithNoPointInside ( int points [ ] [ ] , int N ) { int first = 0 ; int second = 0 ; int third = 0 ; int minD = Integer . MAX_VALUE ; for ( int i = 0 ; i < N ; i ++ ) { if ( i == first ) continue ; int d = getDistance ( points [ i ] [ 0 ] , points [ i ] [ 1 ] , points [ first ] [ 0 ] , points [ first ] [ 1 ] ) ; if ( minD > d ) { minD = d ; second = i ; } } minD = Integer . MAX_VALUE ; for ( int i = 0 ; i < N ; i ++ ) { if ( i == first i == second ) continue ; int 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 ; } } System . out . println ( points [ first ] [ 0 ] + " , ▁ " + points [ first ] [ 1 ] ) ; System . out . println ( points [ second ] [ 0 ] + " , ▁ " + points [ second ] [ 1 ] ) ; System . out . println ( points [ third ] [ 0 ] + " , ▁ " + points [ third ] [ 1 ] ) ; } public static void main ( String [ ] args ) { int points [ ] [ ] = { { 0 , 0 } , { 0 , 2 } , { 2 , 0 } , { 2 , 2 } , { 1 , 1 } } ; int N = points . length ; triangleWithNoPointInside ( points , N ) ; } }