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