Planteamiento del Problema

Dado un tablero de tamaño n × n que contiene m puntos especiales, cada uno con su propio peso. Se necesita hallar una coordenada (fila, columna) que minimice la suma de las distancias Manhattan desde dicha coordenada a todos los puntos especiales, más la suma total de los pesos de los puntos especiales. Formalmente, para cada punto especial pi con coordenadas (xi, yi) y peso wi, se desea minimizar:

∑ |x - x<sub>i</sub>| + |y - y<sub>i</sub>| + ∑ w<sub>i</sub>

Estrategia de Solución

Método 1: Optimización mediante Sumas Acumulativas

La distancia Manhattan es separable por coordenadas, lo que permite procesar filas y columnas de forma independiente. La clave es observar que para un desplazamiento vertical, el cambio en la distancia total depende del balance entre puntos arriba y abajo.

Definimos:

• h[i] = suma de distancias verticales desde una fila i a todos los puntos especiales, multiplicado por un factor z (escala unitaria).
• l[j] = suma de distancias horizontales desde una columna j a todos los puntos.

Para calcular estas sumas eficientemente:

1. Contamos la frecuencia de puntos en cada fila (hnum[k]) y columna (lnum[k]).
2. Construimos prefijos hs[k] y ls[k].
3. Calculamos h[1] y l[1] directamente como:

h[1] = z * ∑ hnum[k] * (k-1)
l[1] = z * ∑ lnum[k] * (k-1)

Luego, para i desde 2 hasta n:

h[i] = h[i-1] + hs[i-1] * z - (m - hs[i-1]) * z
l[i] = l[i-1] + ls[i-1] * z - (m - ls[i-1]) * z

Estas fórmulas reflejan que al bajar una fila, la distancia aumenta por cada punto arriba y disminuye por cada punto abajo.

Finalmente, la coordenada óptima será la fila ansx con h mínimo y columna ansy con l mínimo. El valor total se calcula como:

total = h[ansx] + l[ansy] + sum_weights

Método 2: Aproximación por Mediana Bidimensional

Dado que la distancia Manhattan es spearable, el punto que minimiza la suma de distancias a un conjunto de puntos (sin ponderar) es la mediana de cada coordenada. Incluyenod los pesos, se requiere una mediana ponderada, pero el problema original permite simplificar si los pesos son iguales o se manejan como escalares adicionales.

Pasos:

1. Ordenar las coordenadas x y luego las y de los puntos especiales.
2. Elegir la posición mid = ceil(m/2), que es la mediana aritmética.
3. Calcular la distancia total como:

total = sum_weights + ∑ |x[i] - x[mid]| + |y[i] - y[mid]|

Este método es más simple pero asume que las filas y columnas son independientes, lo cual es válido para Manhattan.

Códigos de Implementación

Código para el Método 1 (Sumas Acumulativas)

#include <bits/stdc++.h>
#define int long long
#define MAXN 100007
using namespace std;

int n, m, z, total_weights;
int row_freq[MAXN], col_freq[MAXN];
int row_prefix[MAXN], col_prefix[MAXN];
int row_cost[MAXN], col_cost[MAXN];

signed main() {
    scanf("%lld%lld%lld", &n, &m, &z);
    for (int i = 0; i < m; i++) {
        int x, y, w;
        scanf("%lld%lld%lld", &x, &y, &w);
        row_freq[x]++;
        col_freq[y]++;
        total_weights += w;
    }
    
    // Prefijos
    for (int i = 1; i <= n; i++) {
        row_prefix[i] = row_prefix[i-1] + row_freq[i];
        col_prefix[i] = col_prefix[i-1] + col_freq[i];
    }
    
    // Calcular costos base para fila 1 y columna 1
    row_cost[1] = 0;
    col_cost[1] = 0;
    for (int i = 1; i <= n; i++) {
        row_cost[1] += row_freq[i] * (i - 1) * z;
        col_cost[1] += col_freq[i] * (i - 1) * z;
    }
    
    // Actualizar usando relaciones recursivas
    for (int i = 2; i <= n; i++) {
        row_cost[i] = row_cost[i-1] + row_prefix[i-1] * z - (m - row_prefix[i-1]) * z;
        col_cost[i] = col_cost[i-1] + col_prefix[i-1] * z - (m - col_prefix[i-1]) * z;
    }
    
    // Encontrar fila y columna óptimas
    int min_row = LLONG_MAX, best_row;
    for (int i = 1; i <= n; i++) {
        if (row_cost[i] < min_row) {
            min_row = row_cost[i];
            best_row = i;
        }
    }
    
    int min_col = LLONG_MAX, best_col;
    for (int i = 1; i <= n; i++) {
        if (col_cost[i] < min_col) {
            min_col = col_cost[i];
            best_col = i;
        }
    }
    
    int resultado = row_cost[best_row] + col_cost[best_col] + total_weights;
    printf("%lld\n%lld %lld\n", resultado, best_row, best_col);
    return 0;
}

Código para el Método 2 (Mediana)

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int MAXM = 100001;

int n, m, z, total_weights;
int xs[MAXM], ys[MAXM];

signed main() {
    scanf("%lld%lld%lld", &n, &m, &z);
    for (int i = 0; i < m; i++) {
        int w;
        scanf("%lld%lld%lld", &xs[i], &ys[i], &w);
        total_weights += w;
    }
    
    int mid = (m + 1) / 2;  // Mediana aritmética
    sort(xs, xs + m);
    sort(ys, ys + m);
    
    int med_x = xs[mid - 1];
    int med_y = ys[mid - 1];
    
    int distance_sum = 0;
    for (int i = 0; i < m; i++) {
        distance_sum += abs(xs[i] - med_x) + abs(ys[i] - med_y);
    }
    
    int result = total_weights + distance_sum;
    printf("%lld\n%lld %lld\n", result, med_x, med_y);
    return 0;
}