Algoritmi de baleiere — o linie care mătură planul

Ideea baleierii

În multe probleme de geometrie ai puncte sau segmente împrăștiate în plan și vrei o proprietate globală (cea mai mică distanță, câte segmente se intersectează). Dacă compari totul cu totul, ajungi la O(n²) — prea lent.

Baleierea (în engleză sweep line) schimbă perspectiva: imaginează o linie verticală care pornește din stânga planului și alunecă spre dreapta, întâlnind puncte. Fiecare întâlnire e un eveniment. Dacă procesezi evenimentele în ordinea coordonatei x, nu mai privești tot planul deodată — te uiți doar la ce e „activ” acum, adică punctele apropiate de linie. Așa transformi o problemă 2D într-o secvență ordonată de evenimente 1D.

Tiparul general

Aproape orice algoritm de baleiere respectă aceiași trei pași:

1. Sortează evenimentele după x. Punctele, capetele segmentelor, marginile dreptunghiurilor — orice „lucru” pe care linia îl întâlnește devine un eveniment cu o coordonată x. Le aranjezi crescător.
2. Mătură unul câte unul. Parcurgi evenimentele în ordinea sortată, ca și cum linia ar trece peste fiecare. La fiecare eveniment iei o decizie.
3. Actualizează structura activă. Ții o structură (de obicei un set sau multiset ordonat) cu „ce e activ acum”. La fiecare eveniment adaugi ce intră în raza de interes și scoți ce a ieșit. Pe această structură mică faci interogările rapide.

Reține ritmul: sortează → mătură → menține activele. Toate variantele de baleiere sunt doar acest tipar, cu definiții diferite pentru „eveniment” și „activ”.

Exemplu: cea mai mică distanță dintre puncte

Ai n puncte cu coordonate întregi și vrei distanța minimă dintre oricare două. Naiv, compari fiecare pereche: O(n²). Cu baleiere cobori la O(n log n).

Schița pe pseudopași:

• Sortezi punctele după x și ții d = cea mai mică distanță găsită până acum.
• Menții o structură activă (ordonată după y) cu punctele din „fereastra” curentă: cele al căror x diferă de punctul curent cu cel mult d.
• Pentru fiecare punct nou, de la stânga la dreapta:
  • Scoți punctele rămase prea în urmă pe x (diferența mai mare decât d) — ele nu mai pot îmbunătăți nimic.
  • Cauți doar punctele cu y în banda [y - d, y + d], cu lower_bound, și actualizezi d dacă găsești ceva mai mic.
  • Adaugi punctul curent în fereastră.

Ideea cheie: „fereastra” e o bandă subțire de lățime d în spatele liniei. Un rezultat clasic spune că în acea bandă sunt puține puncte de verificat, deci munca totală rămâne aproape liniară.

Același tipar prinde și intersecțiile de segmente: evenimentele sunt capetele segmentelor; structura activă ține segmentele tăiate de linie acum, ordonate după y; verifici intersecții doar între vecini.

Implementare C++

Mai jos, cea mai mică distanță cu baleiere și multiset ordonat după y. Comparăm pătratul distanței ca să rămânem pe întregi cât mai mult timp.

#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <cmath>
using namespace std;

struct Punct {
    long long x, y;
};

long long dist2(const Punct& a, const Punct& b) {
    long long dx = a.x - b.x;
    long long dy = a.y - b.y;
    return dx * dx + dy * dy;   // patratul distantei, ramane intreg
}

int main() {
    int n;
    cin >> n;
    vector<Punct> p(n);
    for (int i = 0; i < n; i++) {
        cin >> p[i].x >> p[i].y;
    }

    // pasul 1: sorteaza evenimentele dupa x
    sort(p.begin(), p.end(), [](const Punct& a, const Punct& b) {
        return a.x < b.x;
    });

    long long best = -1;   // patratul celei mai mici distante

    // structura activa: puncte ordonate dupa (y, x)
    auto cmp = [](const Punct& a, const Punct& b) {
        if (a.y != b.y) return a.y < b.y;
        return a.x < b.x;
    };
    multiset<Punct, decltype(cmp)> activ(cmp);

    int stanga = 0;   // marginea ferestrei pe x

    // pasul 2: matura punctele unul cate unul
    for (int i = 0; i < n; i++) {
        // d = distanta minima curenta (ca lungime, pentru fereastra pe x)
        long long d = (best < 0) ? 0 : (long long)ceil(sqrt((double)best));

        // pasul 3a: scoate punctele iesite din fereastra pe x
        if (best >= 0) {
            while (stanga < i && p[i].x - p[stanga].x > d) {
                activ.erase(activ.find(p[stanga]));
                stanga++;
            }
        }

        // pasul 3b: cauta doar vecinii cu y apropiat
        Punct jos = {p[i].x, p[i].y - d};
        auto it = activ.lower_bound(jos);
        while (it != activ.end() && it->y <= p[i].y + d) {
            long long cand = dist2(*it, p[i]);
            if (best < 0 || cand < best) {
                best = cand;
            }
            ++it;
        }

        // pasul 3c: adauga punctul curent in fereastra
        activ.insert(p[i]);
    }

    cout << best << "\n";   // patratul celei mai mici distante
    return 0;
}

Observă cum codul respectă fix tiparul: sort la început, bucla care mătură, iar multiset-ul activ pe care doar adaugi și scoți. Restul e doar interogarea vecinilor.

Complexitate

Costul dominant e sortarea, plus operațiile pe structura ordonată. Asta e tot ce îți trebuie ca să bați soluția naivă O(n²).

Diagramă: puncte sortate după x

Recapitulare

• Baleierea simulează o linie care mătură planul de la stânga la dreapta și procesează evenimente sortate după x, transformând 2D în 1D.
• Tiparul e mereu același: sortează → mătură → menține structura activă, pe care doar adaugi ce intră și scoți ce iese din fereastră.
• Cu un set/multiset ordonat pentru fereastra activă, probleme ca distanța minimă sau intersecțiile de segmente cad de la O(n²) la O(n log n).