Triangle with no point inside | C # 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
using System ; public class GFG { public static int getDistance ( int x1 , int y1 , int x2 , int y2 ) { return ( x2 - x1 ) * ( x2 - x1 ) + ( y2 - y1 ) * ( y2 - y1 ) ; } public static void triangleWithNoPointInside ( int [ ] [ ] points , int N ) { int first = 0 ; int second = 0 ; int third = 0 ; int minD = int . MaxValue ; 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 = int . MaxValue ; 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 ; } } Console . WriteLine ( points [ first ] [ 0 ] + " , ▁ " + points [ first ] [ 1 ] ) ; Console . WriteLine ( points [ second ] [ 0 ] + " , ▁ " + points [ second ] [ 1 ] ) ; Console . WriteLine ( points [ third ] [ 0 ] + " , ▁ " + points [ third ] [ 1 ] ) ; } public static void Main ( string [ ] args ) { int [ ] [ ] points = new int [ ] [ ] { new int [ ] { 0 , 0 } , new int [ ] { 0 , 2 } , new int [ ] { 2 , 0 } , new int [ ] { 2 , 2 } , new int [ ] { 1 , 1 } } ; int N = points . Length ; triangleWithNoPointInside ( points , N ) ; } }