Rotating each point by 45 degrees and calculating prefix sum . Also , finding maximum and minimum x coordinates
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 ) ;