Najbardziej odległe punkty

Niech odległość między dwoma punktami $(x_1, y_1)$ oraz $(x_2, y_2)$ wyraża się wzorem $|x_1 - x_2| + |y_1-y_2|$. Znajdź odległość pomiędzy dwoma najbardziej odległymi punktami w zbiorze, przy takiej definicji odległości.

Zadanie:

Napisz program który:

  • Wczyta ze standardowego wejścia opis zadanego zbioru punktów
  • Wyznaczy największą odległość między parą punktów w tym zbiorze, w metryce miejskiej.
  • Wypisze wynik na standardowe wyjście.

Wejście:

W pierwszym wierszu wejścia znajduje się liczba całkowita N ($2 \leq N \leq 1000000$). W następujących N wierszach występują opisy punktów, po jednym w wierszu.
Każdy opis punktu składa się z dwóch liczb całkowitych $x_i, y_i$ oddzielonych pojedynczym odstępem ($-10^8 \leq x_i, y_i \leq 10^8$). Są to współrzędne odpowiedniego punktu.

Wyjście:

W pierwszym i jedynym wierszu wyjścia powinna znajdować się jedna liczba całkowita: odległość pomiędzy dwoma najbardziej odległymi punktami w metryce miejskiej.

Dodatkowe informacje:

Punktów jest milion, więc aby otrzymać sto punktów za rozwiązanie tego zadania, należy zaimplementować algorytm o złożoności liniowej ( $O(n)$ ). Jeśli nie wiesz co to znaczy - dowiesz się na kółku.

Przykładowa implementacja naiwnego algorytmu o złożoności $O(n^2)$ - proste sprawdzanie odległości między wszystkimi parami punktów - znajduje się niżej. Nie jest to jednak oczekiwany algorytm - jest on zbyt wolny. Może służyć natomiast do sprawdzenia poprawności optymalnego algorytmu.

#include <stdio.h>
#include <stdlib.h>
int n, x[1000000], y[1000000], maxdist=0;
int main(void){
    scanf("%d", &n);
    for(int i=0; i<n; ++i) scanf("%d %d", &x[i], &y[i]);
    for(int i=1; i<n; ++i) for(int j=0; j<i; ++j)
        if(abs(x[i]-x[j])+abs(y[i]-y[j]) > maxdist)
            maxdist = abs(x[i]-x[j]) + abs(y[i]-y[j]);
    printf("%d\n", maxdist);
    return 0;
};

Źródło:
MOKIP 2004/2005, zadanie domowe.