Introducción al Algoritmo Scanline

El algoritmo Scanline, o algoritmo de línea de barrido, es una técnica poderosa utilizada en geometría computacional para resolver problemas que involucran objetos bidimensionales. La idea fundamental es transformar un problema 2D complejo en una secuencia de problemas 1D más sencillos, los cuales pueden ser resueltos eficientemente utilizando estructuras de datos como árboles de segmentos o árboles de Fenwick (BIT).

La estrategia principal consiste en "barrer" el plano con una línea (generalmente vertical u horizontal), procesando los eventos (como los bordes de los objetos) a medida que la línea avanza. Esta técnica es ampliamente aplicable en problemas como la unión de áreas, la unión de perímetros, y el conteo de puntos en rangos 2D, entre otros.

Área de la Unión de Rectángulos

Calcular el área total cubierta por la unión de múltiples rectángulos es un problema clásico resuelto con el algoritmo Scanline. La idea es descomponer la contribución del área por franjas verticales. A medida que una línea de barrido vertical se mueve de izquierda a derecha, el ancho de cada franja es la distancia entre dos coordenadas X consecutivas de los bordes de los rectángulos. La altura de cada franja es la longitud total cubierta por los rectángulos en la coordenada Y actual de la línea de barrido.

Los "eventos" en este caso son los bordes verticales de los rectángulos. Un borde izquierdo suma el intervalo Y del rectángulo al estado actual, mientras que un borde derecho lo resta. Una estructura de datos como un árbol de segmentos se utiliza para mantener la longitud total de los intervalos cubiertos en la línea de barrido. Para manejar coordenadas Y potencialmente grandes, se aplica compresión de coordenadas a las coordenadas Y únicas.

El algoritmo procede de la siguiente manera:

1. Recopilar todos los bordes X de los rectángulos. Cada borde se convierte en un evento con su coordenada X, sus coordenadas Y (inferior y superior), y un tipo de evento (+1 para borde izquierdo, -1 para borde derecho).
2. Recolectar todas las coordenadas Y únicas de los rectángulos para la compresión de coordenadas. Esto mapea las coordenadas Y originales a un rango compacto de índices.
3. Ordenar los eventos por su coordenada X.
4. Iterar a través de los eventos ordenados. Para cada evento, el área acumulada es longitudCubiertaAnterior \* (xActual - xAnterior). Luego, se actualiza el árbol de segmentos con el intervalo Y del evento y su tipo, y se guarda la nueva longitudCubierta para la siguiente iteración.

#include <iostream>
#include <vector>
#include <algorithm>
#include <map> // Podría usarse para compresión si las coords son muy dispersas, pero vector+sort+unique es común

// Usamos long long para el área total para evitar desbordamientos
using long_int = long long;

// Definición de un evento de scanline
struct EventoScanline {
    long_int coordX;
    long_int yInferior, ySuperior;
    int tipo; // +1 para inicio de rectángulo, -1 para fin

    bool operator<(const EventoScanline& otro) const {
        return coordX < otro.coordX;
    }
};

const int MAX_COORD_COUNT = 200005; // Ajustar según las restricciones del problema
long_int longitudCubierta[MAX_COORD_COUNT * 4]; // Árbol de segmentos para longitud cubierta
int contadorCobertura[MAX_COORD_COUNT * 4];    // Contador de cuántos rectángulos cubren un segmento

// Vector para mapear índices comprimidos a coordenadas Y reales
std::vector<long_int> yCoordenadasUnicas;

// Función para actualizar el estado del nodo del árbol de segmentos
void consolidarNodo(int nodo, int indiceIzquierdo, int indiceDerecho) {
    if (contadorCobertura[nodo] > 0) {
        // Si el segmento está cubierto por al menos un rectángulo
        longitudCubierta[nodo] = yCoordenadasUnicas[indiceDerecho] - yCoordenadasUnicas[indiceIzquierdo];
    } else if (indiceIzquierdo + 1 == indiceDerecho) {
        // Si es un nodo hoja y no está cubierto
        longitudCubierta[nodo] = 0;
    } else {
        // Si no está cubierto y no es una hoja, es la suma de sus hijos
        longitudCubierta[nodo] = longitudCubierta[nodo * 2] + longitudCubierta[nodo * 2 + 1];
    }
}

// Función para actualizar el árbol de segmentos
void actualizarArbolSegmentos(int nodo, int rangoIzquierdo, int rangoDerecho, int queryIzquierdo, int queryDerecho, int valor) {
    // Si el rango del nodo está completamente dentro del rango de la consulta
    if (queryIzquierdo <= rangoIzquierdo && rangoDerecho <= queryDerecho) {
        contadorCobertura[nodo] += valor;
        consolidarNodo(nodo, rangoIzquierdo, rangoDerecho);
        return;
    }

    // Si es un nodo hoja y no está completamente dentro del rango de la consulta
    if (rangoIzquierdo + 1 == rangoDerecho) {
        return;
    }

    int rangoMedio = rangoIzquierdo + (rangoDerecho - rangoIzquierdo) / 2;
    // Propagar la actualización a los hijos
    if (queryIzquierdo < rangoMedio) {
        actualizarArbolSegmentos(nodo * 2, rangoIzquierdo, rangoMedio, queryIzquierdo, queryDerecho, valor);
    }
    if (rangoMedio < queryDerecho) {
        actualizarArbolSegmentos(nodo * 2 + 1, rangoMedio, rangoDerecho, queryIzquierdo, queryDerecho, valor);
    }
    consolidarNodo(nodo, rangoIzquierdo, rangoDerecho); // Actualizar el nodo actual después de los hijos
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int numRectangulos;
    std::cin >> numRectangulos;

    std::vector<EventoScanline> eventos;
    eventos.reserve(numRectangulos * 2); // Dos eventos por rectángulo

    for (int i = 0; i < numRectangulos; ++i) {
        long_int x1, y1, x2, y2;
        std::cin >> x1 >> y1 >> x2 >> y2;
        eventos.push_back({x1, y1, y2, 1});  // Borde izquierdo: añadir intervalo
        eventos.push_back({x2, y1, y2, -1}); // Borde derecho: remover intervalo
        yCoordenadasUnicas.push_back(y1);
        yCoordenadasUnicas.push_back(y2);
    }

    // Comprimir coordenadas Y
    std::sort(yCoordenadasUnicas.begin(), yCoordenadasUnicas.end());
    yCoordenadasUnicas.erase(std::unique(yCoordenadasUnicas.begin(), yCoordenadasUnicas.end()), yCoordenadasUnicas.end());

    // Mapear coordenadas Y originales a sus índices comprimidos
    for (auto& evento : eventos) {
        evento.yInferior = std::lower_bound(yCoordenadasUnicas.begin(), yCoordenadasUnicas.end(), evento.yInferior) - yCoordenadasUnicas.begin();
        evento.ySuperior = std::lower_bound(yCoordenadasUnicas.begin(), yCoordenadasUnicas.end(), evento.ySuperior) - yCoordenadasUnicas.begin();
    }

    // Ordenar todos los eventos por coordenada X
    std::sort(eventos.begin(), eventos.end());

    long_int areaTotal = 0;
    long_int ultimaCoordX = eventos[0].coordX; // Coordenada X del evento anterior

    // Iterar a través de los eventos y calcular el área
    for (const auto& evento : eventos) {
        // Acumular el área de la franja anterior
        areaTotal += longitudCubierta[1] * (evento.coordX - ultimaCoordX);

        // Actualizar el árbol de segmentos con el evento actual
        actualizarArbolSegmentos(1, 0, yCoordenadasUnicas.size() - 1, evento.yInferior, evento.ySuperior, evento.tipo);
        
        ultimaCoordX = evento.coordX; // Guardar la coordenada X actual
    }

    std::cout << areaTotal << "\n";

    return 0;
}

Perímetro de la Unión de Rectángulos

Calcular el perímetro de la unión de rectángulos es un poco más complejo que el área, ya que debemos considerar tanto los segmentos horizontales como los verticales del contorno. El algoritmo Scanline se puede adaptar para manejar esto.

La estrategia es similar: barrer con una línea y procesar eventos. Sin embargo, en lugar de solo rastrear la longitud total cubierta, también necesitamos identificar los cambios en la longitud cubierta para los segmentos horizontales, y realizar un segundo paso (o una rotación del problema) para los segmentos verticales.

1. **Perímetro Horiozntal:** Cuando la línea de barrido avanza de x a x', la contribución al perímetro horizontal es la suma de los cambios absolutos en la longitud cubierta. Es decir, |longitudCubiertaActual - longitudCubiertaAnterior|. Este valor se suma al perímetro total. La clave aquí es que un segmento horizontal del contorno aparece cuando un segmento en Y deja de estar cubierto o empieza a estarlo.
2. **Perímetro Vertical:** Para los segmentos verticales, se puede realizar el mismo procedimiento, pero "rotando" el problema. Esto significa que las coordenadas Y se tratan como X y viceversa. Es decir, se ejecuta el algoritmo Scanline dos veces: una con eventos en X para calcular la contribución horizontal, y otra con eventos en Y para la contribución vertical.
3. **Consideraciones de ordenación:** Para el perímetro, es crucial cómo se manejan los bordes coincidentes. Al ordenar los eventos, si dos eventos tienen la misma coordenada X, los eventos de tipo +1 (inicio de rectángulo) deben procesarse antes que los eventos de tipo -1 (fin de rectángulo) si queremos contar el perímetro del "interior". A menudo se usa el tipo como segunda clave de ordenación para manejar esto.
4. **Manejo de coordenadas negativas:** Si las coordenadas pueden ser negativas, es necesario "desplazarlas" sumando una constante grande a todas las coordenadas para que sean positivas y puedan ser usadas como índices en el árbol de segmentos.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath> // Para std::abs

using long_int = long long;

// Constante para desplazar coordenadas negativas
const int OFFSET = 10000;
const int MAX_COORD_VALUE = 20000 + OFFSET * 2; // Max value after offset + a margin
const int MAX_RECTANGLES = 50005; // Número máximo de rectángulos

// Estructura para almacenar los datos de un rectángulo
struct DatosRectangulo {
    long_int x1, y1, x2, y2;
};

// Estructura para un evento de scanline (borde vertical)
struct EventoPerimetro {
    long_int coord; // Coordenada X o Y del evento
    long_int limiteInferior, limiteSuperior; // Límites del segmento en la otra dimensión
    int tipo; // +1 para borde de inicio, -1 para borde de fin

    // Operador de comparación para ordenar eventos
    bool operator<(const EventoPerimetro& otro) const {
        if (coord != otro.coord) {
            return coord < otro.coord;
        }
        // Cuando las coordenadas son iguales, procesar adiciones antes que eliminaciones
        return tipo > otro.tipo;
    }
};

long_int longitudActiva[MAX_COORD_VALUE * 4]; // Longitud total cubierta por segmentos
int contadorSuperposicion[MAX_COORD_VALUE * 4]; // Contador de superposiciones en el segmento

// Función para actualizar el estado de un nodo en el árbol de segmentos
void actualizarEstadoNodo(int nodo, int rangoMin, int rangoMax) {
    if (contadorSuperposicion[nodo] > 0) {
        // Si este nodo está cubierto, su longitud activa es la longitud de su rango
        longitudActiva[nodo] = rangoMax - rangoMin;
    } else if (rangoMin + 1 == rangoMax) {
        // Si es un nodo hoja y no está cubierto
        longitudActiva[nodo] = 0;
    } else {
        // Si no está cubierto y no es hoja, es la suma de sus hijos
        longitudActiva[nodo] = longitudActiva[nodo * 2] + longitudActiva[nodo * 2 + 1];
    }
}

// Función para modificar el árbol de segmentos
void modificarArbolSegmentos(int nodo, int rangoMin, int rangoMax, int queryMin, int queryMax, int valor) {
    // Si el rango del nodo está completamente dentro del rango de la consulta
    if (queryMin <= rangoMin && rangoMax <= queryMax) {
        contadorSuperposicion[nodo] += valor;
        actualizarEstadoNodo(nodo, rangoMin, rangoMax);
        return;
    }

    if (rangoMin + 1 == rangoMax) { // Nodo hoja fuera de rango o ya cubierto/sin cubrir
        return;
    }

    int rangoMedio = rangoMin + (rangoMax - rangoMin) / 2;
    // Propagar a los hijos
    if (queryMin < rangoMedio) {
        modificarArbolSegmentos(nodo * 2, rangoMin, rangoMedio, queryMin, queryMax, valor);
    }
    if (rangoMedio < queryMax) {
        modificarArbolSegmentos(nodo * 2 + 1, rangoMedio, rangoMax, queryMin, queryMax, valor);
    }
    actualizarEstadoNodo(nodo, rangoMin, rangoMax); // Actualizar el nodo actual
}

// Función para calcular la contribución de un componente del perímetro (horizontal o vertical)
long_int calcularComponentePerimetro(int numRectangulos, const std::vector<DatosRectangulo>& rectangulos) {
    // Resetear el árbol de segmentos para cada componente
    for (int i = 0; i < MAX_COORD_VALUE * 4; ++i) {
        longitudActiva[i] = 0;
        contadorSuperposicion[i] = 0;
    }

    std::vector<EventoPerimetro> eventos;
    eventos.reserve(numRectangulos * 2);

    for (int i = 0; i < numRectangulos; ++i) {
        // Desplazar coordenadas para manejar negativos
        long_int x1 = rectangulos[i].x1 + OFFSET;
        long_int y1 = rectangulos[i].y1 + OFFSET;
        long_int x2 = rectangulos[i].x2 + OFFSET;
        long_int y2 = rectangulos[i].y2 + OFFSET;

        // Crear eventos: un borde de inicio y un borde de fin
        eventos.push_back({x1, y1, y2, 1}); // Inicio del rectángulo
        eventos.push_back({x2, y1, y2, -1}); // Fin del rectángulo
    }

    std::sort(eventos.begin(), eventos.end()); // Ordenar eventos por coordenada principal

    long_int perimetroParcial = 0;
    long_int longitudAnterior = 0;
    long_int ultimaCoordPrincipal = eventos[0].coord;

    for (const auto& evento : eventos) {
        // Contribuir a la longitud horizontal
        perimetroParcial += std::abs(longitudActiva[1] - longitudAnterior);

        // Actualizar el árbol de segmentos para el rango [limiteInferior, limiteSuperior]
        modificarArbolSegmentos(1, 0, MAX_COORD_VALUE, evento.limiteInferior, evento.limiteSuperior, evento.tipo);
        
        longitudAnterior = longitudActiva[1]; // Guardar la longitud actual para la próxima iteración
        ultimaCoordPrincipal = evento.coord; // Guardar la coordenada principal actual
    }
    // Es importante añadir la última contribución del último evento
    perimetroParcial += std::abs(longitudActiva[1] - longitudAnterior);


    return perimetroParcial;
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int numRectangulos;
    std::cin >> numRectangulos;

    std::vector<DatosRectangulo> rectangulos(numRectangulos);
    for (int i = 0; i < numRectangulos; ++i) {
        std::cin >> rectangulos[i].x1 >> rectangulos[i].y1 >> rectangulos[i].x2 >> rectangulos[i].y2;
    }

    long_int perimetroTotal = 0;

    // Calcular la contribución de los segmentos horizontales
    perimetroTotal += calcularComponentePerimetro(numRectangulos, rectangulos);

    // Para calcular la contribución de los segmentos verticales, rotamos los rectángulos
    std::vector<DatosRectangulo> rectangulosRotados = rectangulos;
    for (int i = 0; i < numRectangulos; ++i) {
        // Intercambiar X e Y para simular la rotación
        std::swap(rectangulosRotados[i].x1, rectangulosRotados[i].y1);
        std::swap(rectangulosRotados[i].x2, rectangulosRotados[i].y2);
    }

    // Calcular la contribución de los segmentos verticales (ahora horizontales en el problema rotado)
    perimetroTotal += calcularComponentePerimetro(numRectangulos, rectangulosRotados);

    std::cout << perimetroTotal << "\n";

    return 0;
}

Conteo de Puntos en 2D (Orden Parcial Bidimensional)

El problema de conteo de puntos en 2D, también conocido como consulta de rango 2D o problemas de orden parcial 2D, busca contar cuántos puntos cumplen ciertas condiciones (por ejemplo, estar dentro de un rango rectangular). El algoritmo Scanline se puede combinar con un Árbol de Fenwick (BIT) para resolverlo eficientemente.

Un problema común es: "Dado un conjunto de puntos (p\_x, p\_y), y varias consultas (q\_x, q\_y), contar cuántos puntos p satisfacen p\_x <= q\_x y p\_y <= q\_y." Esto se puede extender a rangos rectangulares L\_x <= p\_x <= R\_x y L\_y <= p\_y <= R\_y mediante el principio de inclusión-exclusión.

La estrategia es:

1. Transformar el problema: Considere cada punto a\[i\] del input original como un punto 2D (i, a\[i\]). Una consulta (l, r, x) entonces busca puntos (j, val) tal que l <= j <= r y val <= x.
2. Crear eventos: Se agrupan todos los puntos (como eventos de "adición") y todas las consultas (como eventos de "consulta"). Cada consulta de rango (l, r, x) se descompone en dos eventos: una consulta positiva en r para x (sumar), y una consulta negativa en l-1 para x (restar).
3. Ordenar: Todos estos eventos (puntos y consultas) se ordenan por su coordenada principal (por ejemplo, la coordenada X o el índice j).
4. Procesar: Iterar sobre los eventos ordenados.
   • Cuando se encuentra un punto (j, val), se actualiza un Árbol de Fenwick en la posición val incrementando su valor en 1.
   • Cuando se encuentra un evento de consulta (R, X, tipo), se realiza una consulta en el Árbol de Fenwick para la suma acumulada hasta X. El resultado se almacena y se le aplica el tipo (sumar o restar al resultado final de la consulta original).

El Árbol de Fenwick permite actualizaciones de punto y consultas de suma de prefijos en tiempo logarítmico.

#include <iostream>
#include <vector>
#include <algorithm>

// Tamaño máximo para el array de puntos y el árbol de Fenwick.
// Asegurarse de que sea lo suficientemente grande para las coordenadas máximas.
const int MAX_COORD_VAL = 2000000 + 10; // Ejemplo: 2*10^6 + 10

long long arbolFenwick[MAX_COORD_VAL]; // Árbol de Fenwick

// Función para actualizar un valor en el árbol de Fenwick
void actualizarFenwick(int indice, int delta) {
    while (indice < MAX_COORD_VAL) {
        arbolFenwick[indice] += delta;
        indice += indice & (-indice); // Mover al siguiente padre
    }
}

// Función para consultar la suma de prefijos en el árbol de Fenwick
long long consultarFenwick(int indice) {
    long long suma = 0;
    while (indice > 0) {
        suma += arbolFenwick[indice];
        indice -= indice & (-indice); // Mover al padre anterior
    }
    return suma;
}

// Estructura para almacenar eventos (puntos o consultas)
struct EventoConsulta {
    int idConsulta;     // ID de la consulta original (0 para puntos)
    int limiteDerecho;  // Índice o coordenada X para ordenar eventos
    int valorMaximo;    // Valor Y máximo o valor a consultar/actualizar
    int tipoOperacion;  // +1 para sumar, -1 para restar (para consultas)
                        // +1 para añadir punto (para puntos)
    long long resultadoParcial; // Resultado intermedio para la consulta

    // Operador de comparación para ordenar los eventos por limiteDerecho (X)
    bool operator<(const EventoConsulta& otro) const {
        return limiteDerecho < otro.limiteDerecho;
    }
};

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int numPuntos, numConsultas;
    std::cin >> numPuntos >> numConsultas;

    std::vector<int> valoresPuntos(numPuntos + 1); // Almacena los a[i]
    for (int i = 1; i <= numPuntos; ++i) {
        std::cin >> valoresPuntos[i];
    }

    std::vector<EventoConsulta> eventos;
    eventos.reserve(numPuntos + numConsultas * 2);

    // Añadir los puntos como eventos (idConsulta = 0 para diferenciarlos)
    for (int i = 1; i <= numPuntos; ++i) {
        eventos.push_back({0, i, valoresPuntos[i], 1, 0});
    }

    // Añadir las consultas como eventos (principio de inclusión-exclusión)
    for (int i = 1; i <= numConsultas; ++i) {
        int l, r, x;
        std::cin >> l >> r >> x;
        // Consulta para el límite superior 'r'
        eventos.push_back({i, r, x, 1, 0});
        // Consulta para el límite inferior 'l-1' (se resta el resultado)
        eventos.push_back({i, l - 1, x, -1, 0});
    }

    // Ordenar todos los eventos (puntos y consultas) por su limiteDerecho (coord X)
    std::sort(eventos.begin(), eventos.end());

    std::vector<long long> resultadosFinales(numConsultas + 1, 0);
    int indiceActualPunto = 1; // Para llevar la cuenta de los puntos procesados

    // Procesar los eventos
    for (auto& evento : eventos) {
        // Procesar puntos que caen dentro o antes del limiteDerecho del evento actual
        while (indiceActualPunto <= numPuntos && indiceActualPunto <= evento.limiteDerecho) {
            actualizarFenwick(valoresPuntos[indiceActualPunto], 1); // Añadir el punto al BIT
            indiceActualPunto++;
        }

        // Si es una consulta, realizar la operación
        if (evento.idConsulta != 0) {
            evento.resultadoParcial = consultarFenwick(evento.valorMaximo); // Consultar el BIT
            resultadosFinales[evento.idConsulta] += evento.tipoOperacion * evento.resultadoParcial;
        }
    }

    // Imprimir los resultados finales de las consultas
    for (int i = 1; i <= numConsultas; ++i) {
        std::cout << resultadosFinales[i] << "\n";
    }

    return 0;
}