Geometria Computacional: Conceitos Básicos

Metáfora e Motivação

Problemas de geometria exigem altíssimo cuidado com a representação flutuante no computador (para fugir o máximo possível dos temidos monstros do double/float da arquitetura IEEE 754, e usar inteiros / long long que nunca perdem precisão).

Quando precisamos calcular áreas de polígonos obtusos ou testar se o personagem do jogo colidiu na parede, fugimos das continhas brutas de colégio (Pitágoras ou Senos que obrigam raízes e ângulos de precisão infinita) e nos abraçamos na formidável matemática vetorial.

Primitivas Fundamentais (Matemática Vetorial)

Vetor 2D: A distância mental para sair da origem \(O(0, 0)\) até o ponto \(P(x, y)\). A diferença literal entre dois pontos físicos cria o vetor de deslocamento: \(\vec{AB} = B - A\).
Produto Escalar (Dot Product): \(\vec{A} \cdot \vec{B} = (x_1 \cdot x_2) + (y_1 \cdot y_2)\).
- Devolve um ESCOLAR. Se o valor for \(0\), os vetores são incrivelmente perpendiculares (\(90^{\circ}\)) entre si.
Produto Vetorial 2D (Cross Product): \(\vec{A} \times \vec{B} = (x_1 \cdot y_2) - (x_2 \cdot y_1)\).
- Devolve um ESCOLAR indicando a “força” do giro.
- Valor Positivo: Vire para Esquerda (Counter-Clockwise).
- Valor Negativo: Vire para Direita (Clockwise).
- Valor Zero (\(0\)): São colineares! (Estão na mesma linha). Fundamental para eliminar divisões da nossa vida.
- Mágica da Área: A magnitude exata deste valor é a área de todo o paralelogramo que eles formam! Portanto, a Área de um Triângulo qualquer sem a fórmula de Heron e livre de floats é simplesmente \(\frac{|\vec{A} \times \vec{B}|}{2}\).

Ferramental em C++

Abaixo, montamos o canivete suiço de qualquer maratonista de Geometria:

#include <iostream>
#include <cmath>
#include <cassert>

using namespace std;

// Struct agrupa pra não ficar passando (x1, y1, x2, y2) infinito!
struct Point {
    long long x, y;
    Point(long long _x = 0, long long _y = 0) : x(_x), y(_y) {}
    
    // Sobrecarga matadora: Subtraçao de Pontos cria um array/vetor na origem!
    Point operator- (const Point& outro) const {
        return Point(x - outro.x, y - outro.y);
    }
};

long long crossProduct(Point A, Point B) {
    return A.x * B.y - A.y * B.x;
}

long long dotProduct(Point A, Point B) {
    return A.x * B.x + A.y * B.y;
}

double distanceEuclidian(Point A, Point B) {
    // Pitágoras tradicional
    return hypot(A.x - B.x, A.y - B.y);
}

void executando_testes() {
    Point Origem(0, 0);
    Point P1(0, 5); // Em cima no eixo Y
    Point P2(5, 0); // Lado no eixo X
    
    // Sair de P2 e ir pra P1 exige dobrar a ESQUERDA (Cross positivo)
    assert(crossProduct(P2, P1) > 0);
    
    // P1 e P2 fazem 90 graus na Origem? (Sim, eixos X e Y). DotProduct deve ser vazio!
    assert(dotProduct(P1, P2) == 0);
    
    // Distancia Euclidiana de 0,5 a 5,0 tem lado hipotenusa = sqrt(5^2 + 5^2) = 7.071...
    // Area do triângulo retangulo (Origem -> P1 -> P2) = 5*5 / 2 = 12.5. 
    // Usando O CrossProduct entre (P1) e (P2)
    assert(abs(crossProduct(P1, P2)) / 2.0 == 12.5);

    cout << "[✅] Testes de Primitivas Geometricas (Cross, Dot) operacionais!\n";
}

int main() {
    executando_testes();
    return 0;
}

Problema Clássico de Círculos

Problema: Flores de Fogo Link: Beecrowd 1039

Solução: Não usamos as linhas nem os CrossProducts, mas puramente distância Euclidiana Clássica. O círculo da Flor de raio \(R_2\) sobrevive engolido pelo círculo de fogo do caçador raio \(R_1\), se e somente se, a distância entre seus Centros \((X_1, Y_1)\) e \((X_2, Y_2)\) somado ao raio restrito restrito menor \(R_2 \le R_1\).

Prática Avançada (Geometria Intro)

[Área do Círculo]
- Foco: Precisão com a constante \(\pi\). Use acos(-1) na C++ e fuja do infame 3.14 estático!
- Link: Beecrowd 1002 (Básico)
[Elevador]
- Foco: Lógica de verificação de raios contíguos batendo em quinas flutuantes.
- Link: Beecrowd 1124
[Ponto em Polígono]
- Algoritmos avançados usam o Ray Casting (jogar varreduras pro infinito contando “cruzamentos de borda”). Para Polígonos Convexos, o Cross Product limpo de \(V_{i}\) para \(V_{i+1}\) testando se o Ponto repousa sempre sobre o mesmo espectro do sinal resolve com \(\mathcal{O}(N)\) limpo!