---
tags: geometry, vector, point, plane
---

# Introducción a geometría en programación competitiva

## Definición de vector
- Desde el punto de vista geométrico, un **vector** es una flecha que apunta desde el origen del plano hasta un punto específico. De esa forma vemos que tiene una **longitud** (la distancia desde el origen hasta el punto), **dirección** (la recta que contiene tanto al origen como al punto) y **sentido** (hacia dónde apunta la flecha).
- Desde el punto de vista algebráico, un **vector** $\vec{a}$ es un elemento de $\mathbb{R}^2$ y escribimos $\vec{a}=(a_1, a_2)$, donde $a_1 , a_2 \in \mathbb{R}$ son las **componentes** o **coordenadas** de $\vec{a}$.

:::info
:information_source: **Ejemplo:** Si tenemos el punto $A=(3,4)$, el vector $\vec{a}$ sería el siguiente:


Vemos también que $\vec{a}=(3,4)$ tiene las mismas coordenadas.
:::

## Posición vs desplazamiento
En esencia un punto y un vector son lo mismo, pero un punto solo indica una posición en el plano, mientras que un vector indica un **desplazamiento** entre dos puntos.

- Dado un punto $P$, definimos al **vector de posición** de $P$ respecto del origen $O$ como el vector $\overrightarrow{OP}$ que tendrá las mismas coordenadas del punto $P$. Por simplicidad, también podemos representar a ese vector como $\vec{P}$.
- Dados dos puntos $P$ y $Q$, definimos al **vector de desplazamiento** de $P$ a $Q$ como el vector $\overrightarrow{PQ}$, en donde el origen de la flecha está en $P$ y la punta en $Q$. De esta forma vemos que los vectores no necesariamente comienzan en el origen, sino en donde queramos.

:::info
:information_source: **Ejemplo:** si tenemos que $P=(1,2)$ y $Q=(3,3)$, los vectores de posición y desplazamiento se verán así:


[**Ejemplo interactivo**](https://www.geogebra.org/classic/cawdrpha)

**Pregunta:** ¿Cuáles son las coordenadas de $\overrightarrow{PQ}$?
:::spoiler **Respuesta**
Es la diferencia entre $\vec{Q}$ y $\vec{P}$, es decir, $\overrightarrow{PQ} = \vec{Q} - \vec{P} = (3-1, 3-2) = (2,1)$
:::
:::

## Operaciones básicas
Sean $\vec{a}=(a_1, a_2)$ y $\vec{b} = (b_1, b_2)$ dos vectores. Veamos qué operaciones podemos hacer con ellos:

- **Igualdad:** decimos que $\vec{a} = \vec{b}$ si y solo si $a_1=b_1$ y $a_2=b_2$. Es decir, los vectores son iguales si y solo si sus coordenadas correspondientes son iguales.
:::info
:information_source: **Ejemplo:**
En este caso, $\vec{a}=\vec{b}=(2,1)$. Aunque $\vec{a}$ y $\vec{b}$ no tengan el mismo origen, si sus componentes son iguales, los vectores son iguales.

[**Ejemplo interactivo**](https://www.geogebra.org/classic/sjcvjzer)
:::

- **Suma:** $\vec{a}+\vec{b} = (a_1 + b_1, a_2 + b_2)$. Es decir, para sumar dos vectores solo sumamos sus componentes correspondientes.
:::info
:information_source: **Ejemplo:**
Geométricamente, para sumar dos vectores colocamos el origen de $\vec{b}$ junto a la flecha de $\vec{a}$ y unimos desde el origen de $\vec{a}$ hasta la flecha de $\vec{b}$.

[**Ejemplo interactivo**](https://www.geogebra.org/classic/cgusgakd)
:::

- **Resta:** $\vec{a}-\vec{b} = (a_1 - b_1, a_2 - b_2)$. Es decir, para restar dos vectores solo restamos sus componentes correspondientes, teniendo en cuenta el orden.
:::info
:information_source: 
Geométricamente, para restar dos vectores los colocamos ambos en el mismo origen, y trazamos el vector resultante desde la flecha del segundo a la flecha del primero.

[**Ejemplo interactivo**](https://www.geogebra.org/classic/qwjenbvm)
:::

Y con esta definición, podemos decir que el vector de desplazamiento del punto $P$ al punto $Q$ es el vector $\overrightarrow{PQ} = \vec{Q} - \vec{P}$.

- **Multiplicación por escalar:** $k\vec{a} = (ka_1, ka_2)$ para $k \in \mathbb{R}$. Es decir, para multiplicar un vector por un escalar solo multiplicamos cada componente por dicho escalar.
:::info
:information_source: **Ejemplo:**
Geométricamente, esta operación agranda o reduce el vector sin cambiar su dirección (su sentido se invierte si $k < 0$, se queda igual si $k > 0$ y obtenemos el cero vector si $k=0$).

[**Ejemplo interactivo**](https://www.geogebra.org/classic/q3pwnkcr)
:::

## Magnitud y vector unitario
### Magnitud
Sea $\vec{a}=(x, y)$ un vector:
- La **magnitud**, **longitud** o **módulo** de $\vec{a}$ es la distancia que hay del origen a la flecha de $\vec{a}$. Por el teorema de Pitágoras, la podemos definir como: $\left\lVert{\vec{a}}\right\rVert = \sqrt{x^2+y^2}$.
- De esa definición podemos ver que $\left\lVert{k \vec{a}}\right\rVert = \left\lvert{k}\right\rvert \left\lVert{\vec{a}}\right\rVert$, es decir, al multiplicar el vector por un escalar, la longitud del vector también se multiplica por el valor absoluto del escalar, lo cual tiene sentido geométricamente.

:::info
:information_source: **Ejemplo:** si $\vec{a}=(3,4)$, entonces $\left\lVert{\vec{a}}\right\rVert = \sqrt{3^2+4^2} = \sqrt{9+16} = \sqrt{25} = 5$.
:::

### Vector unitario
Sea $\vec{a}=(x, y)$ un vector:
- Si $\vec{a}$ cumple que $\left\lVert{\vec{a}}\right\rVert = 1$, decimos que es un **vector unitario** y usualmente se denota como $\hat{a}$.
- Para cualquier vector $\vec{a} \neq \vec{0}$ podemos obtener su equivalente unitario, es decir, otro vector $\hat{a}$ cuya dirección y sentido sea el mismo que $\vec{a}$ pero con longitud uno.
- Para hacerlo, simplemente dividimos $\vec{a}$ entre su magnitud, es decir, $\hat{a} = \dfrac{\vec{a}}{\left\lVert{\vec{a}}\right\rVert}$.

:::info
:information_source: **Ejemplo:** si $\vec{a}=(3,4)$, entonces $\hat{a} = \frac{(3, 4)}{5} = \left( \frac{3}{5}, \frac{4}{5} \right)$.

[**Ejemplo interactivo**](https://www.geogebra.org/classic/kyestcnm)
:::

Algunas observaciones:
- Los vectores unitarios son muy útiles, pues en muchas ocasiones sabemos únicamente la dirección y sentido de movimiento, y con solo multiplicar dicho vector por un escalar, avanzamos esa cantidad en la dirección del vector.
- Si conocemos tanto la dirección y sentido como la longitud de un vector, podemos recuperar el vector original así: $\vec{a} = \left\lVert{\vec{a}}\right\rVert \hat{a}$.

## Rotación de vectores y puntos
Sea $\vec{a} = (x,y)$ un vector. Para rotarlo un ángulo de $\theta$ alrededor de su origen en sentido antihorario, usamos la siguiente fórmula:
$$
f(\vec{a}, \theta) = (x \cos \theta - y \sin \theta, x \sin \theta + y\cos \theta)
$$

:::spoiler **Demostración**
Hay muchas formas de demostrar esta fórmula, la más directa usa números complejos, en donde cambiamos el plano *xy* por el plano complejo: el eje *X* pasa a ser el eje real y el eje *Y* pasa a ser el eje imaginario. Entonces, sea $a=x+iy$ el punto representado en este plano. Rotar un número complejo por un ángulo $\theta$ es equivalente a multiplicarlo por $e^{i\theta}$. Por lo tanto:
$$
\begin{align}
ae^{i \theta} &= (x+iy)(\cos \theta + i \sin \theta) \\
&= x \cos \theta + i x \sin \theta + i y \cos \theta - y \sin \theta \\
&= x \cos \theta - y \sin \theta + i(x \sin \theta + y \cos \theta)
\end{align}
$$
Finalmente, regresamos al plano *XY* y obtenemos nuestro resultado.
:::

Geométricamente, el origen del vector se mantiene en su lugar y la flecha es la que rota. Y si queremos rotar un punto $Q$ en el plano alrededor de un punto $P$, lo que hay que hacer es rotar el vector de desplazamiento $\overrightarrow{PQ}$ y al resultado sumarle el vector de posición $\vec{P}$. Es decir:
$$
\vec{Q'} = \vec{P} + f\left(\overrightarrow{PQ}, \theta\right)
$$

:::info
:information_source: **Ejemplo:** si $P=(1,1)$ y $Q=(3,2)$, entonces la rotación de $Q$ alrededor de $P$ con un ángulo de $\theta=78^\circ$ es:
$$
\begin{align}
\overrightarrow{PQ} &= \vec{Q} - \vec{P} = (3,2) - (1,1) = (2,1) \\
f(\overrightarrow{PQ}, \theta) &= (2\cos 78^\circ - 1\sin 78^\circ, 2\sin 78^\circ + 1\cos 78^\circ) \approx (-0.5623, 2.1642) \\
Q' &= \vec{P} + f(\overrightarrow{PQ}, \theta) \approx (1, 1) + (-0.5623, 2.1642) \approx (0.4377, 3.1642)
\end{align}
$$

[**Ejemplo interactivo**](https://www.geogebra.org/classic/aathmntk)
:::

Un caso particular de rotación es cuando rotamos el vector $\vec{a}=(x,y)$ un ángulo de $90^\circ$ a la izquierda. Si aplicamos la fórmula de rotación, el nuevo vector tendrá coordenadas $(-y, x)$. Este vector se llama el **vector perpendicular** a $\vec{a}$, y usualmente se denota como $\vec{a}^\bot$.

## Representación de un punto en C++
Veamos cómo implementar las operaciones básicas que hemos visto hasta ahora en una estructura de datos de $\texttt{C++}$. Declararemos una estructura ``point`` con dos atributos ``x`` y ``y`` para las coordenadas, así como con métodos y sobrecarga de operadores para cada operación:

struct point{
	// Coordenadas del punto (x,y)
	double x, y;
	
	// Constructores
	point(): x(0), y(0) {}
	point(double x, double y): x(x), y(y) {}
	
	// Operaciones básicas
	point operator+(const point & p)const{return point(x + p.x, y + p.y);}
	point operator-(const point & p)const{return point(x - p.x, y - p.y);}
	point operator*(const double & k)const{return point(x * k, y * k);}
	point operator/(const double & k)const{return point(x / k, y / k);}
	
	// Propiedades del punto
	double length()const{return sqrt(x*x + y*y);}
	point unit()const{return (*this) / length();}
	point perp() const{return point(-y, x);}
	point rotate(const double & ang) const{
		return point(x*cos(ang) - y*sin(ang), x*sin(ang) + y*cos(ang));
	}
};

**Detalles de la implementación:**
- En la mayoría de los casos, en los problemas geométricos los puntos en la entrada son todos con componentes enteras. ¿Qué operaciones de las antes vistas siempre devuelven otro punto con coordenadas enteras, y cuáles no necesariamente?
:::spoiler **Respuesta**
Suma, resta, multiplicación por un escalar entero y perpendicular.
:::
- Para comparar dos puntos necesitamos que sus coordenadas sean iguales. ¿En qué casos podemos usar el operador ``==`` directamente y en cuáles no?

	bool operator==(const point & p)const{return x == p.x && y == p.y);}
	bool operator!=(const point & p)const{return !(*this == p);}

:::spoiler **Respuesta**
Cuando ambas coordenadas con enteras es seguro usarlo. Cuando son reales, conviene comparar usando un épsilon.
:::

- Si ya tenemos los operadores de igualdad, convendría tener también los de comparación. ¿Cómo podemos decir que un punto $\vec{a}$ es "mayor" o "menor" a un punto $\vec{b}$? Una solución es usar orden lexicográfico, y resulta que es la que más conviene en la mayoría de los problemas:

	bool operator<(const point & p) const{
		if(x == p.x) return y < p.y;
		return x < p.x;
	}
	bool operator>(const point & p) const{
		if(x == p.x) return y > p.y;
		return x > p.x;
	}

Y de nuevo surge la pregunta, ¿en qué casos podemos usar los operadores ``<`` y ``>`` directamente y en cuáles no?

- Por último, también es útil tener sobrecargados los operadores ``>>`` y ``<<``, para leer un punto de la entrada e imprimirlo a la salida, respectivamente:

istream &operator>>(istream &is, point & p){
	return is >> p.x >> p.y;
}

ostream &operator<<(ostream &os, const point & p){
	return os << "(" << p.x << ", " << p.y << ")";
}

**Ejemplo de uso:**
Veamos cómo quedaría el método ``main`` de un programa que lee dos puntos $P$ y $Q$ y un ángulo $\theta$ de la entrada, e imprime como salida el punto que resulta de rotar el punto $Q$ alrededor de $P$ con un ángulo de $\theta$ en sentido antihorario:

int main(){
	point p, q;
	double theta;
	cin >> p >> q >> theta;
	point q_rotated = p + (q - p).rotate(theta);
	cout << q_rotated << "\n";
	return 0;
}