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
from collections import defaultdict NEW_LINE def is_partition_possible ( n , x , y , w ) : NEW_LINE INDENT weight_at_x = defaultdict ( int ) NEW_LINE max_x = - 2e3 NEW_LINE min_x = 2e3 NEW_LINE for i in range ( n ) : NEW_LINE INDENT new_x = x [ i ] - y [ i ] NEW_LINE max_x = max ( max_x , new_x ) NEW_LINE min_x = min ( min_x , new_x ) NEW_LINE weight_at_x [ new_x ] += w [ i ] NEW_LINE DEDENT sum_till = [ ] NEW_LINE sum_till . append ( 0 ) NEW_LINE for x in range ( min_x , max_x + 1 ) : NEW_LINE INDENT sum_till . append ( sum_till [ - 1 ] + weight_at_x [ x ] ) NEW_LINE DEDENT total_sum = sum_till [ - 1 ] NEW_LINE partition_possible = False NEW_LINE for i in range ( 1 , len ( sum_till ) ) : NEW_LINE INDENT if ( sum_till [ i ] == total_sum - sum_till [ i ] ) : NEW_LINE INDENT partition_possible = True NEW_LINE DEDENT if ( sum_till [ i - 1 ] == total_sum - sum_till [ i ] ) : NEW_LINE INDENT partition_possible = True NEW_LINE DEDENT DEDENT if partition_possible : NEW_LINE INDENT print ( " YES " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " NO " ) NEW_LINE DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT n = 3 NEW_LINE x = [ - 1 , - 2 , 1 ] NEW_LINE y = [ 1 , 1 , - 1 ] NEW_LINE w = [ 3 , 1 , 4 ] NEW_LINE is_partition_possible ( n , x , y , w ) NEW_LINE DEDENT