Find the coordinate that does not belong to any square | Java program for above approach ; Function to find the point that is not a part of the side of a square ; Traverse each pair of coordinates ; Minimize x - coordinate in all the points except current point ; Maximize x - coordinate in all the points except the current point ; Minimize y - coordinate in all the points except current point ; Maximize y - coordinate in all the points except current point ; If x - coordinate matches with other same line ; If y coordinate matches with other same line ; Check if the condition for square exists or not ; Print the output ; Driver Code
import java . util . ArrayList ; class GFG { static class pair < T , V > { T fi ; V se ; pair ( T a , V b ) { this . fi = a ; this . se = b ; } } static void findPoint ( int n , ArrayList < pair < Integer , Integer > > p ) { for ( int i = 0 ; i < n * 4 + 1 ; ++ i ) { int x1 = ( int ) 2e9 , x2 = ( int ) - 2e9 ; int y1 = ( int ) 2e9 , y2 = ( int ) - 2e9 ; for ( int j = 0 ; j < n * 4 + 1 ; ++ j ) if ( i != j ) { x1 = Math . min ( x1 , p . get ( j ) . fi ) ; x2 = Math . max ( x2 , p . get ( j ) . fi ) ; y1 = Math . min ( y1 , p . get ( j ) . se ) ; y2 = Math . max ( y2 , p . get ( j ) . se ) ; } boolean ok = true ; int c1 = 0 , c2 = 0 ; int c3 = 0 , c4 = 0 ; for ( int j = 1 ; j < n * 4 + 1 ; ++ j ) if ( i != j ) { if ( ( p . get ( j ) . fi == x1 || p . get ( j ) . fi == x2 ) || ( ( p . get ( j ) . se == y1 || p . get ( j ) . se == y2 ) ) ) { if ( p . get ( j ) . fi == x1 ) ++ c1 ; if ( p . get ( j ) . fi == x2 ) ++ c2 ; if ( p . get ( j ) . se == y1 ) ++ c3 ; if ( p . get ( j ) . se == y2 ) ++ c4 ; } else ok = false ; } if ( ok && c1 >= n && c2 >= n && c3 >= n && c4 >= n && x2 - x1 == y2 - y1 ) { System . out . println ( p . get ( i ) . fi + " ▁ " + p . get ( i ) . se ) ; } } } public static void main ( String [ ] args ) { int N = 2 ; ArrayList < pair < Integer , Integer > > arr = new ArrayList < > ( ) ; arr . add ( new pair < Integer , Integer > ( 0 , 0 ) ) ; arr . add ( new pair < Integer , Integer > ( 0 , 1 ) ) ; arr . add ( new pair < Integer , Integer > ( 0 , 2 ) ) ; arr . add ( new pair < Integer , Integer > ( 1 , 0 ) ) ; arr . add ( new pair < Integer , Integer > ( 1 , 1 ) ) ; arr . add ( new pair < Integer , Integer > ( 1 , 2 ) ) ; arr . add ( new pair < Integer , Integer > ( 2 , 0 ) ) ; arr . add ( new pair < Integer , Integer > ( 2 , 1 ) ) ; arr . add ( new pair < Integer , Integer > ( 2 , 2 ) ) ; findPoint ( N , arr ) ; } }