Check if a line at 45 degree can divide the plane into two equal weight parts |  ; Checking if a plane can be divide by a line at 45 degrees such that weight sum is equal ; Rotating each point by 45 degrees and calculating prefix sum . Also , finding maximum and minimum x coordinates ; storing weight sum upto x - y point ; Finding prefix sum ; Line passes through i , so it neither falls left nor right . ; Driven code
import java . util . * ; class GFG { static void is_partition_possible ( int n , int x [ ] , int y [ ] , int w [ ] ) { Map < Integer , Integer > weight_at_x = new HashMap < Integer , Integer > ( ) ; int max_x = ( int ) - 2e3 , min_x = ( int ) 2e3 ; for ( int i = 0 ; i < n ; i ++ ) { int new_x = x [ i ] - y [ i ] ; max_x = Math . max ( max_x , new_x ) ; min_x = Math . min ( min_x , new_x ) ; if ( weight_at_x . containsKey ( new_x ) ) { weight_at_x . put ( new_x , weight_at_x . get ( new_x ) + w [ i ] ) ; } else { weight_at_x . put ( new_x , w [ i ] ) ; } } Vector < Integer > sum_till = new Vector < > ( ) ; sum_till . add ( 0 ) ; for ( int s = min_x ; s <= max_x ; s ++ ) { if ( weight_at_x . get ( s ) == null ) sum_till . add ( sum_till . lastElement ( ) ) ; else sum_till . add ( sum_till . lastElement ( ) + weight_at_x . get ( s ) ) ; } int total_sum = sum_till . lastElement ( ) ; int partition_possible = 0 ; for ( int i = 1 ; i < sum_till . size ( ) ; i ++ ) { if ( sum_till . get ( i ) == total_sum - sum_till . get ( i ) ) partition_possible = 1 ; if ( sum_till . get ( i - 1 ) == total_sum - sum_till . get ( i ) ) partition_possible = 1 ; } System . out . printf ( partition_possible == 1 ? "YES " ▁ : ▁ " NO "); } public static void main ( String [ ] args ) { int n = 3 ; int x [ ] = { - 1 , - 2 , 1 } ; int y [ ] = { 1 , 1 , - 1 } ; int w [ ] = { 3 , 1 , 4 } ; is_partition_possible ( n , x , y , w ) ; } }