Емблема центру  www.olymp.vinnica.ua     netoi.org.ua
Центр олімпіад школярів в Iнтернеті
Likt-PMG17
м.Вiнниця


Годинник
 
NewSubnet

Задача newSubNet

Після модифікацї мережв Sumnet є прямокутною сіткою в кожному з вузлів якої розміщено комп'ютер. Канали з'язку утворюють своєрідні "квадрати". Пакети проходять вздовж сторони такого квадрата за одиницю часу. Всі комп'ютери постійно працюють на прийом, а де-які з них одночасно починають надсилати в мережу пакти в режимі трансляції, тобто таким чином, що вони без будь-яких затримок на своєму шляху раніше чи пізніше потраплять на кожен з комп'ютерів мережі. Який мінімальний час пройде, поки якийсь з комп'ютерів не отримає всі пакети. Мережа має розміри 2000*2000 (тобто в мережі 4000000 комп'ютерів).

2<=N<=1000 - кількість комп'ютерів, що одночасно відправляють пакети 0<= Xi,Yi<= 2000 - кординати і-го комп'ютера

Технічні умови: Програма зчитує з клавіатури число N, а далі N пар цілих чисел - координати комп'ютерів, що надсилають пакети. Всі числа розділено пропусками. Програма виводить на екран єдине число - шукану величину.

Приклад.

Введення> 3 1 1 5 1 3 3
Виведення> 2

(через дві одиниці часу пакети від усіх надсилаючих комп'ютерів зберуться на комп'ютері з координатами (3,1))


Задача newSubnet

После модификации сеть SubNet представляет собой прямоугольную сетку, в каждом из узлов которой размещен компьютер. Каналы связи образуют своеобразные "квадраты". Пакеты  проходят  вдоль стороны такого квадрата за еденицу времени. Все компьютеры постоянно работают на прием, а некоторые из них одновременно посылают в сеть пакеты в режиме трансляции,  таким образом, чтоб они без каких-либо задержек на своем пути рано или поздно попадают на каждый компьютер сети. Какое минимальное время пройдет, пока какой-то из компьютеров не получит все пакеты. Сеть имеет размеры 2000*2000 ( в сети 4000000 компьютеров).

2<=N<=1000 - количество компьютеров, которые одновременно отправляют пакети 0<= Xi,Yi<= 2000 - координаты і-го компьютера

Техническое условие: Программа считывает с клавиатуры число N, а далее N пар целых чисел - координаты компьютеров, которые посылают пакеты. Все числа разделены пробелами. Программа выводит на экран единственное число - искомую величину.

Пример.

Ввод> 3 1 1 5 1 3 3
Вывод> 2

(через две единицы времени пакеты от всех отсылающих компьютеров соберутся на компьютере с координатами (3,1))



© Всеукраїнський віртуальний центр олімпіад школярів "ОЛІМП"