All Manhattan Distances

Explicación

Nuestra respuesta se puede escribir como:

\sum_{1\le i<j\le n} (|x_j-x_i|+|y_j-y_i|) = \sum_{1\le i<j\le n} |x_j-x_i|+\sum_{1\le i<j\le n}|y_j-y_i|

Las contribuciones de las coordenadas $x$ y de las coordenadas $y$ se pueden tratar por separado. Mantendremos dos arreglos ordenados, uno con los valores de $x$ y otro con los de $y$ . Recordemos la definición explícita del valor absoluto:

|A - B| = \left\{ \begin{array}{ll} A - B, & A \ge B\\ B-A, & A<B \end{array} \right.

Al recorrer cada arreglo en orden creciente, sabemos exactamente que el valor $c$ aporta $+c$ a las distancias de los valores anteriores a $c$ , y aporta $-c$ a las distancias de los valores posteriores. Como los arreglos están ordenados, sabemos cuántos valores hay antes y después de cada valor $c$ , lo que nos permite sumar estas contribuciones directamente tanto para los valores de $x$ como para los de $y$ .

Implementación

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

C++


#include <bits/stdc++.h>
 
using namespace std;
 
// Tipo de datos para entero de 128 bits
void print_int128(__int128 x) {
	if (x == 0) {
		cout << 0;
		return;
	}
 
	if (x < 0) {
		cout << '-';
		x = -x;
	}
 
	string res;
	while (x > 0) {
		res += (x % 10) + '0';
		x /= 10;
	}
 
	reverse(res.begin(), res.end());
	cout << res;
}
 
int main() {
	int n;
	cin >> n;
 
	vector<long long> x(n), y(n);
	for (int i = 0; i < n; i++) { cin >> x[i] >> y[i]; }
 
	sort(x.begin(), x.end());
	sort(y.begin(), y.end());
 
	// BigInt en C++
	__int128 sum(0);
	for (int i = 0; i < n; i++) {
		// (i - 1) signos + y (n - i) signos -
		long long contrib = 2 * i - (n - 1);
		sum = sum + contrib * (x[i] + y[i]);
	}
 
	print_int128(sum);
}