Escrito por Leonardo Paes, Thiago Mota e Lúcio Figueiredo
Um dos tipos de problemas recorrentes na programação competitiva são os problemas de geometria computacional. Geometria computacional é uma aplicação direta da geometria analítica na informática. Nessa aula, iremos estudar pontos e vetores no plano cartesiano, que são a base na geometria computacional.
Pontos
Pontos situados no plano cartesiano são representados por pares de inteiros $$(x, y)$$, normalmente chamados de coordenadas. Os pontos são adimensionais e podem representar inúmeras coisas como coordenadas em um mapa ou funções matemáticas como, por exemplo, $$y = f(x)$$.
A coordenada $$x$$ de um ponto $$(x, y)$$ é comumente chamada abscissa do ponto, e representa o deslocamento horizontal de tal ponto no plano. Já a coordenada $$y$$ é denominada ordenada do ponto, e representa o deslocamento vertical do ponto no plano.
No plano acima estão presentes os pontos $$(x, y)$$: $$(1, 3)$$ e $$(2, 2)$$. (Site utilizado: Desmos).
Em C++, iremos representar pontos usando o tipo pair, como representado no código abaixo:
Distância entre dois pontos
A distância entre dois pontos, mais conhecida como distância euclidiana, é definida como o tamanho da reta que liga os dois pontos. Para calcular a distância entre eles, podemos utilizar o Teorema de Pitágoras nas componentes $$x$$ e $$y$$.
Clique aqui para conferir a prova do Teorema de Pitágoras:
Teorema de Pitágoras: Dado um triângulo retângulo com catetos de comprimento $$A$$ e $$B$$ e hipotenusa de comprimento $$C$$, vale que $$A^2 + B^2 = C^2$$.
Prova:
Seja $$ABCD$$ um quadrado de lado $$L$$ tal que $$A + B = L$$.
A área do quadrado $$ABCD$$ é $$(A+B)^2$$ e a área de um triângulo vermelho é $$A*B/2$$.
Assim, a área do quadrado cinza é $$(A+B)^2 – 2*A*B = C^2$$.
Expandindo: $$A^2 + 2*A*B + B^2 – 2*A*B = C^2$$.
Logo: $$A^2 + B^2 = C^2$$, como queríamos demonstrar.
Observe o exemplo abaixo:
Imagine que queremos calcular a distância $$d$$ entre os pontos $$(1, 3)$$ (digamos, ponto $$A$$) e $$(2, 2)$$ (ponto $$C$$). Defina o ponto $$B$$ (ponto $$(1, 2)$$ na figura) como a interseção da reta horizontal que passa por $$C$$ com a reta vertical que passa em $$A$$.
Definindo $$d_x$$ como o comprimento do segmento ligando $$B$$ e $$C$$ e $$d_y$$ como o comprimento do segmento ligando $$A$$ e $$B$$, temos que $$d_y = 3 – 2 = 1$$ e $$d_x = 2 – 1 = 1$$. Como o triângulo formado ao ligar os pontos $$A$$, $$B$$ e $$C$$ é retângulo, podemos aplicar o Teorema de Pitágoras:
$$\begin{cases} d^2 = d_x^2 + d_y^2 \\ d^2 = 1^2 + 1^2 \\ d^2 = 1 + 1 = 2 \\ d = \sqrt{2} \end{cases}$$
Logo, a distância entre os pontos $$A$$ e $$C$$ é $$\sqrt{2}$$.
De modo geral, para dois pontos $$A$$ e $$B$$ de coordenadas $$(A_x, A_y)$$ e $$(B_x, B_y)$$, respectivamente, temos que $$dist(A, B) = \sqrt{(A_x-B_x)^2 + (A_y-B_y)^2}$$, onde $$dist(A, B)$$ é a distância entre os dois pontos.
O código a seguir calcula a distância entre dois pontos, utilizando a fórmula acima:
Obs: Em C++ , para pontos de distância $$d$$, normalmente é utilizado o $$d^2$$ ao invés do $$d$$, pois $$d$$ pode ser um número decimal (tipo double), e isso pode causar imprecisão na realização de cálculos.
Vetores
Um vetor é utilizado para representar grandezas vetoriais. Uma grandeza vetorial, diferentemente de um número, possuí módulo, direção e sentido. Observe a seguinte imagem:
O módulo do vetor é representado por seu tamanho, ou seja, a distância entre os dois pontos que representam o vetor. Já a direção é a reta que o vetor está localizado, então o vetor $$\overrightarrow{AB}$$ tem a mesma direção do vetor $$\overrightarrow{BA}$$; o que muda nesse caso é o sentido deles, já que um vai de $$A$$ pra $$B$$ e o outro de $$B$$ para $$A$$.
Normalmente representamos o vetor apenas como um ponto $$(x, y)$$, pois utilizamos a origem do vetor como sendo a origem do plano cartesiano $$(0, 0)$$, ou seja, o módulo do vetor representado pelo ponto é a distância entre os pontos $$(0, 0)$$ e $$(x, y)$$, o que deixa as contas bem mais simples. Quando a origem de um vetor dado não se localiza no ponto $$(0, 0)$$, precisaremos realizar uma translação no vetor, tópico abordado nas seções abaixo.
Soma e subtração de vetores
A soma de dois vetores $$(x_1, y_1)$$ e $$(x_2, y_2)$$ é representado pelo vetor da soma de suas coordenadas, ou seja, o vetor $$(x_1 + x_2, y_1 + y_2)$$. Como um exemplo, a soma dos vetores $$(1, 3)$$ e $$(3, 2)$$ é o vetor $$(4, 5)$$.
Um truque para somar dois vetores geometricamente é colocar um dos vetores com a origem na ponta do outro vetor e ligar a origem de um com a extremidade do outro. Observe a imagem:
Como podemos ver, o vetor $$\vec{w}$$ é a soma dos vetores $$\vec{u}$$ e $$\vec{v}$$. Aplicando o truque citado acima, obteremos a seguinte figura:
Ao colocar a origem do vetor $$\vec{v}$$ na extremidade do vetor $$\vec{u}$$, podemos ligar o início do vetor $$\vec{u}$$ com a extremidade do vetor $$\vec{v}$$, obtendo, assim, o vetor $$\vec{w}$$.
A subtração de vetores é definida de maneira semelhante à soma. O resultado da subtração de vetores $$(x_1, y_1)$$ e $$(x_2, y_2)$$ é o vetor $$(x_1-x_2, y_1-y_2)$$.
Para desenhar a subtração de dois vetores no plano, trataremos a subtração dos vetores $$\vec{u}$$ e $$\vec{v}$$ como sendo a soma do vetor $$\vec{u}$$ com o vetor $$(-\vec{v})$$, que possui mesmo módulo e direção que $$\vec{v}$$, com sentido contrário. Assim, realizaremos o mesmo truque da soma de vetores, invertendo o sentido do vetor $$\vec{v}$$.
Translação de vetores
Na seção de soma e subtração de vetores, assumimos que a origem de cada vetor se localizava no ponto $$(0, 0)$$; no entanto, este nem sempre é o caso. Para trabalhar com vetores com origens em pontos quaisquer, iremos mover, ou seja, transladar as suas origens para o ponto $$(0, 0)$$, mantendo os seus módulos, direções e sentidos.
Ao realizarmos a translação da origem do vetor $$\vec{u}$$ para $$(0, 0)$$, as coordenadas de sua extremidade irão ser alteradas. Portanto, o que queremos descobrir (de modo a manter as propriedades do vetor $$\vec{u}$$) são as coordenadas da sua extremidade após a translação.
Defina $$(u_x, u_y)$$ como as coordenadas da extremidade de $$\vec{u}$$ antes da translação e $$(v_x, v_y)$$ como as coordenadas da origem de $$\vec{u}$$. Como iremos levar o ponto $$(v_x, v_y)$$ para $$(0, 0)$$, notamos que a extremidade do vetor irá se deslocar em $$-v_x$$ no sentido horizontal e em $$-v_y$$ no sentido vertical, já que mantemos o módulo, a direção e o sentido de $$\vec{u}$$. Portanto, concluímos que as coordenadas da extremidade de $$\vec{u}$$ após a translação serão $$(u_x – v_x, u_y – v_y)$$. Desta forma, conseguimos uma maneira de trabalhar apenas com vetores de origem em $$(0, 0)$$.
A figura abaixo mostra o vetor $$\vec{u}$$ após a translação.
