Maximum Manhattan Distances

Solución

Sean $A(x_A,y_A)$ y $B(x_B,y_B)$ dos puntos. La distancia de Manhattan (o del taxista) entre ellos es $d = |x_B-x_a|+|y_B-y_A|$. Suele ser buena idea definir los casos del valor absoluto:

Ahora distinguimos cuatro casos para el valor de la distancia, según $x$ e $y$:

Por tanto, para cada punto importan la suma y la diferencia de las coordenadas. Así, llevaremos el máximo y el mínimo de la suma y de la diferencia. Cuando aparece un punto nuevo, actualizamos los valores. El máximo de los valores $\text{maxsum}-\text{minsum}$ y $\text{maxdiff}-\text{mindiff}$ es la respuesta para los cuatro casos.

Implementación

Complejidad temporal: $\mathcal{O}(N)$

#include <bits/stdc++.h>
using namespace std;
 
int main() {
	int n;
	cin >> n;
 
	int x, y;
	cin >> x >> y;
 
	long long min_sum, max_sum;
	long long min_diff, max_diff;
 
	min_sum = max_sum = x + y;
	min_diff = max_diff = x - y;
 
	cout << max(max_sum - min_sum, max_diff - min_diff) << '\n';
 
	for (int i = 2; i <= n; i++) {
		int x, y;
		cin >> x >> y;
 
		long long sum = x + y;
		long long diff = x - y;
 
		if (sum < min_sum) {
			min_sum = sum;
		} else if (sum > max_sum) {
			max_sum = sum;
		}
 
		if (diff < min_diff) {
			min_diff = diff;
		} else if (diff > max_diff) {
			max_diff = diff;
		}
 
		cout << max(max_sum - min_sum, max_diff - min_diff) << '\n';
	}
}