text: 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 Program
code: #include <bits/stdc++.h> NEW_LINE using namespace std ; void is_partition_possible ( int n , int x [ ] , int y [ ] , int w [ ] ) { map < int , int > weight_at_x ; int max_x = -2e3 , min_x = 2e3 ; for ( int i = 0 ; i < n ; i ++ ) { int new_x = x [ i ] - y [ i ] ; max_x = max ( max_x , new_x ) ; min_x = min ( min_x , new_x ) ; weight_at_x [ new_x ] += w [ i ] ; } vector < int > sum_till ; sum_till . push_back ( 0 ) ; for ( int x = min_x ; x <= max_x ; x ++ ) { sum_till . push_back ( sum_till . back ( ) + weight_at_x [ x ] ) ; } int total_sum = sum_till . back ( ) ; int partition_possible = false ; for ( int i = 1 ; i < sum_till . size ( ) ; i ++ ) { if ( sum_till [ i ] == total_sum - sum_till [ i ] ) partition_possible = true ; if ( sum_till [ i - 1 ] == total_sum - sum_till [ i ] ) partition_possible = true ; } printf ( partition_possible ? " YES STRNEWLINE " : " NO STRNEWLINE " ) ; } int main ( ) { 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 ) ; return 0 ; }