Another Contest 3 Problem 2 - Camelot - Olympiads Online Judge

Another Contest 3 Problem 2 - Camelot

Points: 15

Time limit: 1.0s

PyPy 3 1.5s

Memory limit: 256M

Problem type

In the game of chess, a king can move horizontally, vertically, or diagonally by one unit. More specifically, if a king is at $(x, y)$ $(x, y)$ , their $x$ $x$ -coordinate can change by at most one and their $y$ $y$ -coordinate can change by at most one in a single move.

There are $N$ $N$ kings on an infinite chessboard where each square can fit an infinite number of kings, and they wish to meet up at a single location. In one second, exactly one king can move by one unit - all other kings must stay still. Compute the minimum amount of time needed for all the kings to meet up.

Constraints

$1 \le N \le 10^6$ $1 \leq N \leq 10^{6}$

$-10^9 \le x_i, y_i \le 10^9$ $- 10^{9} \leq x_{i}, y_{i} \leq 10^{9}$

Kings may already be in the same square.

Input Specification

The first line contains a single positive integer, $N$ $N$ .

Each of the next $N$ $N$ lines contains two space-separated integers, $x_i$ $x_{i}$ and $y_i$ $y_{i}$ , indicating that a king is at $(x_i, y_i)$ $(x_{i}, y_{i})$ .

Output Specification

Output the minimum time in seconds needed for all the kings to convene.

Sample Input

Copy

Sample Output

Copy

Comments

7

injust commented on Dec. 16, 2018, 1:40 a.m. ← edit 2 →

Python one-linerino!