Intersecții de drepte și segmente — testul cu orientare

Produsul vectorial ca test de orientare

Cea mai folositoare unealtă din toată geometria de concurs e produsul vectorial a doi vectori. Pentru trei puncte O, A, B cu coordonate întregi îl definim ca:

cross(O, A, B) = (xA - xO) * (yB - yO) - (yA - yO) * (xB - xO)

Nu te interesează valoarea lui, ci semnul. El îți spune cum „virezi” când mergi de la O spre A și apoi te uiți la B:

• cross > 0 — B e la stânga direcției O → A (viraj trigonometric);
• cross < 0 — B e la dreapta;
• cross == 0 — cele trei puncte sunt coliniare (pe aceeași dreaptă).

Pentru că lucrăm cu coordonate întregi, păstrăm rezultatul pe long long și testăm doar semnul. Așa evităm complet erorile de rotunjire pe care le-ar aduce double.

Intersecția a două drepte

O dreaptă infinită prin punctele A și B are direcția dată de vectorul AB = (xB - xA, yB - yA). Două drepte fie sunt paralele, fie se taie în exact un punct.

Testul e simplu: două drepte sunt paralele dacă direcțiile lor sunt coliniare, adică produsul vectorial al direcțiilor (înmulțirea încrucișată) este zero:

(xB - xA) * (yD - yC) - (yB - yA) * (xD - xC) == 0

Dacă această cantitate e diferită de zero, dreptele se intersectează într-un singur punct. Dacă e zero, sunt paralele (sau chiar suprapuse, dacă mai sunt și coliniare). Reține: pentru drepte infinite nu contează unde cad capetele — doar panta, adică direcția. Aici se ascunde o capcană pe care o vedem mai jos.

Intersecția a două segmente

Un segment are capete: nu se întinde la infinit. Două segmente AB și CD se taie efectiv (intersecție „proprie”) dacă și numai dacă fiecare segment trece de partea cealaltă a celuilalt. Traducem asta în patru produse vectoriale:

• d1 = cross(C, D, A) și d2 = cross(C, D, B) — de ce parte a dreptei CD cad A și B;
• d3 = cross(A, B, C) și d4 = cross(A, B, D) — de ce parte a dreptei AB cad C și D.

Segmentele se intersectează propriu dacă d1 și d2 au semne opuse ȘI d3 și d4 au semne opuse. „Semne opuse” înseamnă că produsul lor este strict negativ.

Mai rămân cazurile coliniare: când vreunul dintre produse e 0, un capăt stă chiar pe dreapta celuilalt segment. Atunci trebuie să verificăm dacă acel capăt cade în interiorul segmentului (test de încadrare pe coordonate, numit „on segment”). Așa prindem și atingerile la capete și suprapunerile parțiale.

Exemplu pas cu pas

Fie segmentele AB cu A = (0, 0), B = (4, 4) și CD cu C = (0, 4), D = (4, 0). Sunt cele două diagonale ale unui pătrat — clar se taie în centru.

• cross(A, B, C) = (4-0)*(4-0) - (4-0)*(0-0) = 16 - 0 = 16 (pozitiv);
• cross(A, B, D) = (4-0)*(0-0) - (4-0)*(4-0) = 0 - 16 = -16 (negativ);
• semne opuse → C și D sunt de o parte și de alta a lui AB. Bun.
• cross(C, D, A) = (4-0)*(0-4) - (0-4)*(0-0) = -16 - 0 = -16 (negativ);
• cross(C, D, B) = (4-0)*(4-4) - (0-4)*(4-0) = 0 + 16 = 16 (pozitiv);
• semne opuse → A și B sunt de o parte și de alta a lui CD. Se intersectează.

Acum un caz care nu se taie: CD cu C = (5, 0), D = (5, 4) (un segment vertical departe, la dreapta).

• cross(A, B, C) = (4)*(0) - (4)*(5) = -20;
• cross(A, B, D) = (4)*(4) - (4)*(5) = 16 - 20 = -4;
• ambele negative → C și D sunt de aceeași parte a lui AB. Nu se taie.

Implementare C++

#include <iostream>
#include <algorithm>   // pentru min si max
using namespace std;

struct Punct {
    long long x, y;
};

// produsul vectorial (xA-xO)(yB-yO) - (yA-yO)(xB-xO)
// semnul spune orientarea lui B fata de directia O->A
long long cross(Punct O, Punct A, Punct B) {
    return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
}

// semnul unui numar: -1, 0 sau 1
int semn(long long v) {
    if (v > 0) return 1;
    if (v < 0) return -1;
    return 0;
}

// verifica daca P, coliniar cu segmentul AB, cade pe segment
bool peSegment(Punct A, Punct B, Punct P) {
    return min(A.x, B.x) <= P.x && P.x <= max(A.x, B.x) &&
           min(A.y, B.y) <= P.y && P.y <= max(A.y, B.y);
}

// true daca segmentele AB si CD se intersecteaza (inclusiv atingeri)
bool seIntersecteaza(Punct A, Punct B, Punct C, Punct D) {
    int d1 = semn(cross(A, B, C));
    int d2 = semn(cross(A, B, D));
    int d3 = semn(cross(C, D, A));
    int d4 = semn(cross(C, D, B));

    // cazul propriu: capetele cad de o parte si de alta
    if (d1 != d2 && d3 != d4) return true;

    // cazuri coliniare: un capat sta chiar pe celalalt segment
    if (d1 == 0 && peSegment(A, B, C)) return true;
    if (d2 == 0 && peSegment(A, B, D)) return true;
    if (d3 == 0 && peSegment(C, D, A)) return true;
    if (d4 == 0 && peSegment(C, D, B)) return true;

    return false;
}

int main() {
    Punct A = {0, 0}, B = {4, 4};   // prima diagonala
    Punct C = {0, 4}, D = {4, 0};   // a doua diagonala

    cout << seIntersecteaza(A, B, C, D) << "\n";   // 1 (se taie in centru)

    Punct E = {5, 0}, F = {5, 4};   // segment vertical, departe
    cout << seIntersecteaza(A, B, E, F) << "\n";   // 0 (nu se taie)

    return 0;
}

Complexitate

Toți pașii sunt câteva înmulțiri și comparații, fără bucle. Testul de intersecție a două segmente rulează deci în O(1) timp și O(1) memorie. Dacă ai n segmente și vrei toate perechile care se taie, faci O(n²) apeluri ale acestei funcții O(1).

Recapitulare

• cross(O, A, B) pe long long dă, prin semn, orientarea lui B față de O → A: stânga, dreapta sau coliniar.
• Două drepte se intersectează dacă direcțiile nu sunt coliniare (înmulțirea încrucișată diferită de zero); două segmente se taie dacă fiecare trece de partea cealaltă a celuilalt (semne opuse), plus cazurile coliniare cu peSegment.
• Lucrezi numai cu numere întregi și semne — fără double, fără rotunjiri — iar testul rulează în O(1).