Решение задачи Столица с Яндекс Контест

Без пояснения   Просмотров: 2215

В некотором царстве, в некотором государстве было N городов, и все они, судя по главной карте императора, имели целые координаты. В те годы леса были дремучие, дороги же строить умели только параллельно осям координат, так что расстояние между двумя городами определялось как |x1 - x2| + |y1 - y2|.

Император решил построить N+1-ый город и сделать его столицей своего государства, при этом координаты столицы также должны быть целыми. Место для столицы следует выбрать так, чтобы среднее арифметическое расстояний между столицей и остальными городами было как можно меньше. Однако, разумеется, столицу нельзя строить на месте существующего города.

Нелегкая задача выбрать место для столицы поручена Вам.

Код 

n = int(input())
arr_x, arr_y = [], []
for i in range(n):
    a, b = input().split()
    arr_x.append(int(a))
    arr_y.append(int(b))

med_x = sorted(arr_x)[n // 2]
med_y = sorted(arr_y)[n // 2]
ans = 10**10
for x in range(med_x - 20, med_x + 20):
    for y in range(med_y - 20, med_y + 20):
        plus = 0
        for i in range(n):
            if x == arr_x[i] and y == arr_y[i]:
                plus = -1
                break
            plus += abs(arr_x[i] - x) + abs(arr_y[i] - y)
        if plus < ans and plus != -1:
            ans = plus
            x_one = x
            y_one = y
print(x_one, y_one)

         

Администратор Photo Автор: Администратор



Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться



info@mycod.net   Карта сайта   Правообладателям
Заявка на расчет
×

или напишите нам прямо сейчас:

Написать в MAX
Написать в Telegram
Написать в WhatsApp