8994. Taksówka na Manhattanie [TAXIMAN]

Zadanie:
https://pl.spoj.com/problems/TAXIMAN

Skrócony opis problemu:

Mając dane $n$ punktów, znajdź odległość między dwoma najbardziej oddalonymi od siebie punktami (w metryce Manhattan - np. odległość między $(1;1)$ a $(2;2)$ to 2, bo trzeba iść 1 w górę i 1 w prawo).

Rozwiązanie naiwne:

Dla każdej pary punktów sprawdzamy odległość między nimi ze wzoru: $d(A,B) = |x_A-x_B|+|y_A-y_B|$ i wybieramy największą z nich.

Złożoność: $O(n^2)$, bo sprawdzamy każdą parę punktów, a jest ich $\frac{n(n-1)}{2}$.

Rozwiązanie sprytne:

Znajdujemy najmniejszy prostokąt, który zawiera wszystkie punkty. Ogranicza się to do znalezienia najmniejszych oraz największych współrzędnych x i y (będą to 4 wartości). Następnie znajdujemy w czasie liniowym 4 punkty, które są najbliższe rogom tego prostokąta. Na koniec, mając te 4 punkty, wypisujemy większą z dwóch odległości: od lewego dolnego do prawego górnego oraz od lewego górnego do prawego dolnego.

Złożoność: $O(n)$, bo prostokąt znajdujemy w czasie liniowym, jak i najbliższe rogom punkty.

Rozwiązanie sprytne nr 2:

Określmy odległość każdego punktu od $(0;0)$. Jest to $|y_i|+|x_i|$. Mając 2 punkty możemy obliczyć odległość między nimi za pomocą ich odległości od $(0;0)$. Np. dla $(1;2)$ i $(6;7)$ wartości to odpowiednio 3 i 13. Odległość między nimi to zatem $|3-13|=10$. ALE dla punktów $(1;7)$, $(6;-1)$ to nie działa. Dlaczego? Bo dla pierwszej pary odcinek wygląda jak / a dla drugiej jak \ . W pierwszym przypadku jest dobrze, bo odległość między pierwszym punktem i $(0;0)$ ma wspólny początek z odległością między drugim punktem i $(0;0)$, a w drugim przypadku niekoniecznie. Jak możemy to naprawić? Obracając układ współrzędnych albo, konkretniej, oś OX, zamieniając znaki wszystkim x. Dla punktów $(1;7)$, $(6;-1)$ obliczamy zatem dwie wartości: $y_i+x_i$ (8 dla pierwszego punktu i 5 dla drugiego) oraz $y_i-x_i$ (6 dla pierwszego punktu i -7 dla drugiego). Z ich pomocą możemy obliczyć ich odległość - jest to większa z $|8-5|=3$ i $|6+7|=13$, a więc 13. Możemy więc znaleźć $min$ i $max$ dla $y_i+x_i$ oraz $min2$ i $max2$ dla $y_i-x_i$ w czasie liniowym. Co z tym robimy? Porównujemy $|max-min|$ oraz $|max2-min2|$ i wybieramy większe z nich. Jest to nasz wynik.

Złożoność: $O(n)$, bo znajdujemy $min$, $max$, $min2$, $max2$ w czasie liniowym.

Algorytm:

int main()
{
    int n, x, y;
    long long max = -2e9, max2 = -2e9, min = 2e9, min2 = 2e9;
    
    get(n);
    while(n--)
    {
        get(x); get(y);
        if(y+x > max)
            max = y+x;
        if(y+x < min)
            min = y+x;
        if(y-x > max2)
            max2 = y-x;
        if(y-x < min2)
            min2 = y-x;
    }
    print(max2(abs(max-min), abs(max2-min2)));
}

Rozwiązanie sprytne nr 3:

Autorem tego rozwiązania jest paladin, a wzory zostały podane przez Zordona.

Można posłużyć się metryką maksimum. Jest to taka metryka, w której odległość wyraża się następującym wzorem:

$$d(A,B) = \max\left(|x_A-x_B|, |y_A-y_B|\right)$$

Aby otrzymać najbardziej odległe punkty wystarczy zatem znaleźć 4 skrajne punkty (po lewej, po prawej, u góry i na dole) a następnie wypisać większą z dwóch odległości między nimi (lewy-prawy, góra-dół).

Jak jednak zamienić metrykę Manhattan na metrykę maksimum? Ano prostym wzorem:

$$(x,y) \mapsto (x-y, x+y)$$

Potrzebne uzasadnienie dlaczego to działa. Nie krępujcie się pisać w komentarzach.

Złożoność: $O(n)$, bo dla każdego punktu zamieniamy go na metrykę maksimum w czasie stałym, a potem w czasie liniowym znajdujemy skrajne punkty.

Algorytm:

int main()
{
    int n, x, y;
    long long maxx = -2e9, maxy = -2e9, minx = 2e9, miny = 2e9;
    
    get(n);
    while(n--)
    {
        get(x, y);
        x -= y; y += x+y;
        if(y > maxy)
            maxy = y;
        if(y < miny)
            miny = y;
        if(x > maxx)
            maxx = x;
        if(x < minx)
            minx = x;
    }
    print(max2(abs(maxx-minx), abs(maxy-miny)));
}

Jak widać, rozwiązanie to jest tożsame do poprzedniego (kod jest taki sam praktycznie).