Нужно ускорить/опитимизировать код

def max_distance(trap_x, trap_y, coordinates):
    distance = 0
    for x, y in coordinates:
        distance = max(distance, abs(trap_x - x) + abs(trap_y - y))
    return distance
 
 
def main():
    M = int(input())
    coordinates = [tuple(map(int, input().split())) for _ in range(M)]
 
    x_min, _ = min(coordinates, key=lambda c: (c[0], c[1]))
    x_max, _ = max(coordinates, key=lambda c: (c[0], c[1]))
    _, y_min = min(coordinates, key=lambda c: (c[1], c[0]))
    _, y_max = max(coordinates, key=lambda c: (c[1], c[0]))
 
    min_time = float('inf')
    result_x, result_y = 0, 0
 
    for trap_x in range(x_min, x_max + 1):
        for trap_y in range(y_min, y_max + 1):
            cur_time = max_distance(trap_x, trap_y, coordinates)
            if cur_time < min_time:
                min_time = cur_time
                result_x, result_y = trap_x, trap_y
 
    print(result_x, result_y)
 
 
if __name__ == "__main__":
    main()

def read_input():
    M = int(input())
    locations = []
    for _ in range(M):
        x, y = map(int, input().split())
        locations.append((x, y))
    return locations
 
def find_best_section(locations):
    avg_x = sum(x for x, y in locations) / len(locations)
    avg_y = sum(y for x, y in locations) / len(locations)
    
    best_section = (round(avg_x), round(avg_y))
    return best_section
 
locations = read_input()
best_section = find_best_section(locations)
 
print(*best_section)

from math import sqrt
 
 
def main():
    n = int(input().strip())
    locations = []
    for _ in range(n):
        x, y = map(int, input().strip().split())
        locations.append((x, y))
 
    min_x, max_x, min_y, max_y =\
        float('inf'), float('-inf'), float('inf'), float('-inf')
 
    for loc in locations:
        min_x = min(min_x, loc[0])
        max_x = max(max_x, loc[0])
        min_y = min(min_y, loc[1])
        max_y = max(max_y, loc[1])
 
    if max_x - min_x > max_y - min_y:
        rotation = 45 * sqrt(2)
        min_y = (min_y + min_x) / 2 - rotation / 2
        max_y = (max_y + max_x) / 2 + rotation / 2
 
    trap_x, trap_y = (min_x + max_x) // 2, (min_y + max_y) // 2
 
    print(trap_x, trap_y)
 
 
if __name__ == "__main__":
    main()

def main():
    M = int(input())
    coordinates = [tuple(map(int, input().split())) for _ in range(M)]
    
    #x_min, _ = min(coordinates, key=lambda c: (c[0], c[1]))
    #x_max, _ = max(coordinates, key=lambda c: (c[0], c[1]))
    #_, y_min = min(coordinates, key=lambda c: (c[1], c[0]))
    #_, y_max = max(coordinates, key=lambda c: (c[1], c[0]))
    x, y = zip(*coordinates)
    x_min, x_max = min(x), max(x)
    y_min, y_max = min(y), max(y)
    min_time = float('inf')
    result_x = 0 # любое число
    
    for trap_y in range(y_min, y_max + 1):
        cur_time = max_distance(result_x, trap_y, coordinates)
        if cur_time < min_time:
            min_time = cur_time
            result_y = trap_y
    
    for trap_x in range(x_min, x_max + 1):
        cur_time = max_distance(trap_x, result_y, coordinates)
        if cur_time < min_time:
            min_time = cur_time
            result_x, result_y = trap_x, result_y
    
    print(result_x, result_y)
    print(min_time)

def find_best_trap_location(coord_list):
    n = len(coord_list)
    coord_list.sort(key=lambda x: x[0])
    if n % 2 == 1:
        median_x = coord_list[n // 2][0]
    else:
        median_x = (coord_list[n // 2][0] + coord_list[n // 2 - 1][0]) // 2
 
    coord_list.sort(key=lambda y: y[1])
    if n % 2 == 1:
        median_y = coord_list[n // 2][1]
    else:
        median_y = (coord_list[n // 2][1] + coord_list[n // 2 - 1][1]) // 2
 
    return median_x, median_y
 
 
def read_input():
    m = int(input())
    coords = [tuple(map(int, input().split())) for _ in range(m)]
    return coords
 
 
def write_output(answer):
    print(str(answer[0]) + ' ' + str(answer[1]))
 
 
def main():
    coord_list = read_input()
    best_location = find_best_trap_location(coord_list)
    write_output(best_location)
 
 
if __name__ == "__main__":
    main()

def read_inputs():
    M = int(input())
    locations = []
    for i in range(M):
        x, y = map(int, input().split())
        locations.append((x, y))
 
    return M, locations
 
 
def find_best_section(M, locations):
    min_x = max_x = locations[0][0]
    min_y = max_y = locations[0][1]
 
    for loc in locations:
        min_x = min(min_x, loc[0])
        max_x = max(max_x, loc[0])
        min_y = min(min_y, loc[1])
        max_y = max(max_y, loc[1])
 
    result_x = (min_x + max_x) // 2
    result_y = (min_y + max_y) // 2
 
    return result_x, result_y
 
 
def main():
    M, locations = read_inputs()
    x, y = find_best_section(M, locations)
    print(x, y)
 
 
if __name__ == "__main__":
    main()

from sys import stdin
 
def distance(x1, y1, x2, y2):
    return max(abs(x1 - x2), abs(y1 - y2))
 
def count_time(mid_x, mid_y, locations):
    return max(distance(mid_x, mid_y, x, y) for x, y in locations)
 
def bin_search(locations):
    x_min, x_max = min(x for x, y in locations), max(x for x, y in locations)
    y_min, y_max = min(y for x, y in locations), max(y for x, y in locations)
 
    best_time = float("inf")
    best_loc = None
 
    while x_min <= x_max and y_min <= y_max:
        mid_x = (x_min + x_max) // 2
        mid_y = (y_min + y_max) // 2
 
        curr_time = count_time(mid_x, mid_y, locations)
 
        if curr_time < best_time:
            best_time = curr_time
            best_loc = mid_x, mid_y
 
        if mid_x < mid_y:
            x_min, y_max = mid_x + 1, mid_y - 1
        else:
            x_max, y_min = mid_x - 1, mid_y + 1
 
    return best_loc
 
def main():
    M = int(stdin.readline().strip())
    locations = [tuple(map(int, stdin.readline().strip().split())) for _ in range(M)]
 
    solution = bin_search(locations)
    print(solution[0], solution[1])
 
if __name__ == "__main__":
    main()

def max_distance(trap_x, trap_y, coordinates):
    distance = 0
    for x, y in coordinates:
        distance = max(distance, abs(trap_x - x) + abs(trap_y - y))
    return distance
 
 
def binary_search(min_value, max_value, target_distance, coordinates, is_x_search):
    while min_value < max_value:
        mid = (min_value + max_value) // 2
 
        if is_x_search:
            distance = max_distance(mid, target_distance, coordinates)
        else:
            distance = max_distance(target_distance, mid, coordinates)
 
        if is_x_search:
            next_distance = max_distance(mid + 1, target_distance, coordinates)
        else:
            next_distance = max_distance(target_distance, mid - 1, coordinates)
 
        if distance <= next_distance:
            max_value = mid
        else:
            min_value = mid + 1
 
    return min_value
 
 
def main():
    M = int(input())
    coordinates = [tuple(map(int, input().split())) for _ in range(M)]
 
    x, y = zip(*coordinates)
    x_min, x_max = min(x), max(x)
    y_min, y_max = min(y), max(y)
 
    result_x = binary_search(x_min, x_max, 0, coordinates, True)
    result_y = binary_search(y_min, y_max, result_x, coordinates, False)
 
    print(result_x, result_y)
 
 
if __name__ == "__main__":
    main()

with open('input.txt') as f:
    c = int(f.readline())
    xy =[list(map(int, c.split())) for i, c in enumerate(f.readlines())]
    cx, cy = list(zip(*xy))
    print(sorted(cx)[c//2], sorted(cy)[c//2])
    
def max_distance(trap_x, trap_y, coordinates):
    distance = 0
    for x, y in coordinates:
        distance += abs(trap_x - x) + abs(trap_y - y)
    return distance
 
 
def main(M, coordinates):
    x, y = zip(*coordinates)
    x_min, x_max = min(x), max(x)
    y_min, y_max = min(y), max(y)
    min_time = float('inf')
    result_y = 1000# любое число
    
    for trap_x in range(x_min, x_max + 1):
        cur_time = max_distance(trap_x, result_y, coordinates)
        if cur_time < min_time:
            min_time = cur_time
            result_x = trap_x
        
    for trap_y in range(y_min, y_max + 1):
        cur_time = max_distance(result_x, trap_y, coordinates)
        if cur_time < min_time:
            min_time = cur_time
            result_y = trap_y
    
    print(result_x, result_y)
    print(min_time)
 
 
if __name__ == "__main__":
    main(c, xy)