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
function is_partition_possible ( n , x , y , w ) { let weight_at_x = new Map ( ) ; let max_x = - 2e3 , min_x = 2e3 ; for ( let i = 0 ; i < n ; i ++ ) { let 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 . has ( new_x ) ) { weight_at_x . set ( new_x , weight_at_x . get ( new_x ) + w [ i ] ) ; } else { weight_at_x . set ( new_x , w [ i ] ) ; } } let sum_till = [ ] ; sum_till . push ( 0 ) ; for ( let s = min_x ; s <= max_x ; s ++ ) { if ( weight_at_x . get ( s ) == null ) sum_till . push ( sum_till [ sum_till . length - 1 ] ) ; else sum_till . push ( sum_till [ sum_till . length - 1 ] + weight_at_x . get ( s ) ) ; } let total_sum = sum_till [ sum_till . length - 1 ] ; let partition_possible = 0 ; for ( let i = 1 ; i < sum_till . length ; i ++ ) { if ( sum_till [ i ] == total_sum - sum_till [ i ] ) partition_possible = 1 ; if ( sum_till [ i - 1 ] == total_sum - sum_till [ i ] ) partition_possible = 1 ; } document . write ( partition_possible == 1 ? " " : " " ) ; } let n = 3 ; let x = [ - 1 , - 2 , 1 ] ; let y = [ 1 , 1 , - 1 ] ; let w = [ 3 , 1 , 4 ] ; is_partition_possible ( n , x , y , w ) ;