Distanța dintre două puncte

De ce contează?

Doi pomi în curte: cât de departe sunt unul de altul? Întinzi o sfoară dreaptă între ei. Lungimea sforii e distanța în linie dreaptă — și se calculează cu o formulă pe care o știi deja din clasă: teorema lui Pitagora.

Formula distanței

Distanța dintre A(xA, yA) și B(xB, yB) e ipotenuza unui triunghi dreptunghic cu catetele |xB − xA| și |yB − yA|:

d = √( (xB − xA)² + (yB − yA)² )

Observația-cheie

Diferența pe orizontală și cea pe verticală sunt catetele; distanța în linie dreaptă e ipotenuza. Pitagora aplicată direct în plan.

Exemplu concret

Pentru A(0, 0) și B(3, 4):

latura	3	4	5
rol	dx	dy	d

dx = 3, dy = 4 (catetele); d = √(9+16) = √25 = 5 (ipotenuza).

dx = 3 - 0 = 3
dy = 4 - 0 = 4
d  = sqrt(3*3 + 4*4) = sqrt(25) = 5

Implementare C++

#include <iostream>
#include <cmath>
using namespace std;

int main() {
    long long x1 = 0, y1 = 0, x2 = 3, y2 = 4;
    long long dx = x2 - x1;
    long long dy = y2 - y1;
    long long distLaPatrat = dx * dx + dy * dy;  // long long: evita overflow

    double d = sqrt((double)distLaPatrat);
    cout << d << endl;                            // 5
    return 0;
}

Trucul: compară pătratele, nu rădăcinile

Când doar compari distanțe (care e mai aproape?), nu calcula sqrt deloc. Dacă d1 < d2, atunci și d1² < d2². Pătratele sunt întregi → comparație exactă și rapidă:

long long distSq(long long x1, long long y1, long long x2, long long y2) {
    long long dx = x2 - x1, dy = y2 - y1;
    return dx * dx + dy * dy;          // fara sqrt
}
// cel mai apropiat punct de origine = cel cu distSq minim

Indiciu

sqrt întoarce un double — lent și cu mici erori de rotunjire. Pentru „cine e mai aproape” sau „distanța e exact k”, lucrează cu pătratul întreg și compară distSq == k*k.

Complexitate

Operație	Timp	Spațiu
O distanță (sau pătratul ei)	O(1)	O(1)
Cel mai apropiat dintre `n` puncte	O(n)	O(1)

Greșeli frecvente

Capcane reale:

Overflow la pătrat. dx*dx cu dx de 10⁹ dă 10¹⁸ → folosește long long; chiar și int*int intermediar se sucește.
Folosești sqrt când nu trebuie. La comparații, pătratul întreg e exact și rapid; sqrt introduce erori de rotunjire.
Compari double cu ==. d == 5.0 poate eșua din rotunjire. Compară pătratul: distSq == 25.
Uiți modulul la catete. Nu contează — le ridici la pătrat oricum, deci semnul dispare; dar nu confunda dx cu |dx| în alte formule.

Recapitulare

Distanța = √(dx² + dy²), Pitagora aplicată cu catetele dx și dy.
Pentru comparații folosește pătratul întreg (distSq) — exact, rapid, fără sqrt.
Ridicarea la pătrat a coordonatelor mari cere long long, altfel overflow.