Primitivas de geometría

Hay que conocer operaciones como el producto cruz y el producto punto.

Recursos
Fuente	Recurso	Notas
CF	C++ - std::complex	breve descripción de las operaciones
CPH	29 - Geometry	Números complejos, puntos y rectas, polígonos, distancias
CF	Point Struct	código, ejemplos
cp-algo	Geometry - Elementary Operations
CPC	12 - geometry	básicos, área de polígono, punto en polígono
CF	vlecomte - Geometry Handbook	parte del material es bastante avanzado
CP2	7.2, 7.3 - Basic Geo, Polygons

Mis plantillas

Ubicación de un punto

Hecho	Fuente	Nombre	Dificultad	Tags	Solución
	CSES	Point Location Test	Fácil	Geometry	en el módulo

Explicación

Para comprobar la ubicación de $P$ respecto de la recta $P_1$ $P_2$ usamos la siguiente fórmula: $(P.y - P_1.y) * (P_2.x - P_1.x) - (P.x - P_1.x) * (P_2.y - P_1.y)$ Si es igual a $0$ significa que $P$ , $P_1$ y $P_2$ son colineales. En caso contrario el signo del valor indica si $P$ está debajo de la recta — negativo — o encima de la recta — positivo.

Demostración

Sea $m_1=\frac{P_1.y - P_2.y}{P_1.x - P_2.x}$ la pendiente de la función lineal que pasa por los puntos $P_1$ y $P_2$ y $m_2=\frac{P_2.y - P.y}{P_2.x - P.x}$ la pendiente de la función lineal que pasa por los puntos $P_2$ y $P$ .

Los puntos son colineales si y solo si las pendientes son iguales, es decir $m_1 = m_2 \Leftrightarrow \frac{P_1.y - P_2.y}{P_1.x - P_2.x} = \frac{P_2.y - P.y}{P_2.x - P.x} \Leftrightarrow (P_1.y - P_2.y) * (P_2.x - P.x) = (P_1.x - P_2.x) * (P_1.x - P_2.x) \Leftrightarrow (P_1.y - P_2.y) * (P_2.x - P.x) - (P_1.x - P_2.x) * (P_1.x - P_2.x) = 0$ . Y de esta forma obtuvimos la fórmula mencionada antes.

Esta fórmula no solo nos dice si los puntos son colineales, sino también dónde está ubicado el punto $P$ .

Dem

Implementación

Complejidad temporal: $\mathcal{O}(1)$ para cada caso de prueba.

C++Python


#include <bits/stdc++.h>
using namespace std;
 
 
// BeginCodeSnip{Point Class}
struct Point {
	int x, y;
	Point(int a = 0, int b = 0) : x(a), y(b) {}
 
	friend istream &operator>>(istream &in, Point &p) {
		int x, y;
		in >> p.x >> p.y;
		return in;
	}
};
// EndCodeSnip
 
long long collinear(Point p, Point p1, Point p2) {
	return 1LL * (p.y - p1.y) * (p2.x - p1.x) - 1LL * (p.x - p1.x) * (p2.y - p1.y);
}
 
int main() {
	int test_num;
	cin >> test_num;
	for (int t = 0; t < test_num; t++) {
		Point p1, p2, p3;
		cin >> p1 >> p2 >> p3;
 
		if (collinear(p1, p2, p3) == 0) {
			cout << "TOUCH" << '\n';
		} else if (collinear(p1, p2, p3) < 0) {
			cout << "RIGHT" << '\n';
		} else {
			cout << "LEFT" << '\n';
		}
	}
}


class Point:
	def __init__(self, x: int = 0, y: int = 0):
		self.x = x
		self.y = y
 
 
def collinear(p: Point, p1: Point, p2: Point) -> int:
	return (p.y - p1.y) * (p2.x - p1.x) - (p.x - p1.x) * (p2.y - p1.y)
 
 
for _ in range(int(input())):
	points = list(map(int, input().split()))
	p1 = Point(points[0], points[1])
	p2 = Point(points[2], points[3])
	p3 = Point(points[4], points[5])
 
	result = collinear(p1, p2, p3)
	if result == 0:
		print("TOUCH")
	elif result < 0:
		print("RIGHT")
	else:
		print("LEFT")

Intersección de segmentos

Hecho	Fuente	Nombre	Dificultad	Tags	Solución
	CSES	Line Segment Intersection	Normal	Geometry	en el módulo

Explicación

Podemos descartar rápidamente la intersección de segmentos tratándolos como rectángulos que tienen los segmentos como diagonales, lo cual se hace de forma sencilla. Si resulta que los rectángulos se intersectan, entonces simplemente comprobamos si los extremos de un segmento están en lados distintos del otro segmento.

Implementación

C++


#include <bits/stdc++.h>
using namespace std;
 
// BeginCodeSnip{Point Class}
struct Point {
	int x, y;
	Point(int a = 0, int b = 0) : x(a), y(b) {}
 
	friend istream &operator>>(istream &in, Point &p) {
		int x, y;
		in >> p.x >> p.y;
		return in;
	}
};
// EndCodeSnip
 
int sign(long long num) {
	if (num < 0) {
		return -1;
	} else if (num == 0) {
		return 0;
	} else {
		return 1;
	}
}
 
long long trigonometric_sense(Point p, Point p1, Point p2) {
	return sign(1LL * (p1.x - p.x) * (p2.y - p.y) - 1LL * (p2.x - p.x) * (p1.y - p.y));
}
 
// Check if the rectangles with [P1, P2] and [P3, P4] as diagonals intersect
bool quick_check(Point p1, Point p2, Point p3, Point p4) {
	int x1, x2, x3, x4, y1, y2, y3, y4;
	x1 = min(p1.x, p2.x), x2 = max(p1.x, p2.x);
	y1 = min(p1.y, p2.y), y2 = max(p1.y, p2.y);
	x3 = min(p3.x, p4.x), x4 = max(p3.x, p4.x);
	y3 = min(p3.y, p4.y), y4 = max(p3.y, p4.y);
	return x2 < x3 || x4 < x1 || y2 < y3 || y4 < y1;
}
 
bool check(Point p1, Point p2, Point p3, Point p4) {
	if (trigonometric_sense(p1, p2, p3) * trigonometric_sense(p1, p2, p4) > 0) {
		return false;
	}
	if (trigonometric_sense(p3, p4, p1) * trigonometric_sense(p3, p4, p2) > 0) {
		return false;
	}
	return true;
}
 
int main() {
	int test_num;
	cin >> test_num;
	for (int t = 0; t < test_num; t++) {
		Point p1, p2, p3, p4;
		cin >> p1 >> p2 >> p3 >> p4;
 
		if (quick_check(p1, p2, p3, p4)) {
			puts("NO");
		} else if (check(p1, p2, p3, p4)) {
			puts("YES");
		} else {
			puts("NO");
		}
	}
}

Área de un polígono

Hecho	Fuente	Nombre	Dificultad	Tags	Solución
	CSES	Polygon Area	Normal	Geometry, Math	en el módulo

Explicación

Podemos usar la fórmula del cordón (Shoelace) .

Implementación

Complejidad temporal: $\mathcal{O}(N)$

C++Python


#include <bits/stdc++.h>
using namespace std;
 
// BeginCodeSnip{Point Class}
struct Point {
	int x, y;
	Point(int a = 0, int b = 0) : x(a), y(b) {}
 
	friend istream &operator>>(istream &in, Point &p) {
		int x, y;
		in >> p.x >> p.y;
		return in;
	}
};
// EndCodeSnip
 
int main() {
	int n;
	cin >> n;
	vector<Point> points(n);
	for (auto &p : points) { cin >> p; }
	points.push_back(points[0]);
 
	long long area = 0;
	for (int i = 0; i < n; i++) {
		area +=
		    (1LL * points[i].x * points[i + 1].y - 1LL * points[i].y * points[i + 1].x);
	}
	cout << labs(area) << '\n';
}


class Point:
	def __init__(self, x: int = 0, y: int = 0):
		self.x = x
		self.y = y
 
 
n = int(input())
points = []
for _ in range(n):
	x, y = map(int, input().split())
	points.append(Point(x, y))
 
points.append(points[0])
 
area = 0
for i in range(n):
	area += points[i].x * points[i + 1].y - points[i].y * points[i + 1].x
 
print(abs(area))

Ubicación de un punto respecto de un polígono

Hecho	Fuente	Nombre	Dificultad	Tags	Solución
	CSES	Point in Polygon	Normal	Geometry, Math	en el módulo

Explicación

Podemos lanzar un rayo desde el punto $P$ en cualquier dirección fija (normalmente se va hacia la derecha). Si el punto está fuera del polígono, el rayo intersectará sus aristas un número par de veces. Si el punto está dentro del polígono, entonces intersectará las aristas un número impar de veces.

Este enfoque se llama ray casting (lanzamiento de rayos).

Implementación

C++


#include <bits/stdc++.h>
 
using namespace std;
 
// BeginCodeSnip{Point Class}
struct Point {
	int x, y;
	Point(int a = 0, int b = 0) : x(a), y(b) {}
 
	friend istream &operator>>(istream &in, Point &p) {
		int x, y;
		in >> p.x >> p.y;
		return in;
	}
};
// EndCodeSnip
 
bool on_segment(const Point &p, const Point &p1, const Point &p2) {
	int a = min(p1.x, p2.x);
	int b = max(p1.x, p2.x);
	int x = min(p1.y, p2.y);
	int y = max(p1.y, p2.y);
	return 1LL * (p.y - p1.y) * (p2.x - p1.x) == 1LL * (p.x - p1.x) * (p2.y - p1.y) &&
	       a <= p.x && p.x <= b && x <= p.y && p.y <= y;
}
 
long long trigonometric_sense(Point p, Point p1, Point p2) {
	return 1LL * (p1.x - p.x) * (p2.y - p.y) - 1LL * (p2.x - p.x) * (p1.y - p.y);
}
 
int main() {
	int n, m;
	cin >> n >> m;
	vector<Point> poly(n);
	for (Point &p : poly) { cin >> p; }
	for (int j = 0; j < m; j++) {
		Point p;
		cin >> p;
		// Intersection count
		int cnt = 0;
		bool flag = false;
		for (int i = 0; i < n; i++) {
			int j = (i + 1) % n;
			if (on_segment(p, poly[i], poly[j])) {
				flag = true;
				break;
			}
			if (poly[i].y <= p.y && p.y < poly[j].y &&
			    trigonometric_sense(p, poly[i], poly[j]) > 0)
				cnt++;
			if (poly[j].y <= p.y && p.y < poly[i].y &&
			    trigonometric_sense(p, poly[j], poly[i]) > 0)
				cnt++;
		}
		if (flag) {
			cout << "BOUNDARY" << '\n';
		} else {
			cout << (cnt % 2 ? "INSIDE" : "OUTSIDE") << '\n';
		}
	}
}

Puntos de retículo en un polígono

Hecho	Fuente	Nombre	Dificultad	Tags	Solución
	CSES	Polygon Lattice Points	Normal	Geometry	en el módulo

Explicación

Enfoquémonos primero en los puntos de retículo sobre la frontera del polígono. Procesaremos cada arista por separado. La cantidad de intersecciones de una recta con puntos de retículo es el máximo común divisor de $P_1.x - P_2.x$ y $P_1.y - P_2.y$ .

Demostración

Se puede demostrar usando la función lineal. Denotar los extremos del segmento con ( $x_1$ , $y_1$ ) y ( $x_2$ , $y_2$ ). La función tiene la siguiente forma: &f(x) = ax + b&. La pendiente de $f(x)$ , en nuestro caso $a$ , es $\frac{y_1-y_2}{x_1-x_2}$ , así que $f(x)$ se convierte en $f(x) = \frac{y_1-y_2}{x_1-x_2} * x + b$ .

Esto significa que cada punto a lo largo de la recta tiene la siguiente forma: $(x, f(x))$ , que se ha convertido en $(x, \frac{y_1-y_2}{x_1-x_2} * x + b)$ . El número $x$ puede ser cualquier entero, pero &f(x)& no. Para que sea un punto de retículo &f(x)& tiene que ser un entero, al eliminar la fracción lo que resulta es que $x$ es divisible por $x_1 - x_2$ .

Ahora que conocemos la cantidad de puntos de retículo en la frontera, podemos hallar la cantidad de puntos de retículo dentro del polígono usando el teorema de Pick . Denotemos $A$ el área del polígono, $i$ la cantidad de puntos enteros interiores y $b$ la cantidad de puntos enteros en su frontera. Entonces, según el teorema de Pick, tenemos la siguiente ecuación: $A = i + b/2 - 1$ . Cambiando un poco el orden obtenemos $i = A - b/2 + 1$ . Ya hallamos $b$ y, como probablemente ya se resolvió Polygon Area de arriba, $A$ se puede calcular usando el producto cruz.

Implementación

Complejidad temporal: $\mathcal{O}(N \log P)$ , donde $P$ es la diferencia máxima entre coordenadas de los puntos.

C++Python


#include <bits/stdc++.h>
 
using namespace std;
 
// BeginCodeSnip{Point Class}
struct Point {
	int x, y;
	Point(int a = 0, int b = 0) : x(a), y(b) {}
	Point operator-(const Point &other) { return {x - other.x, y - other.y}; }
	friend istream &operator>>(istream &in, Point &p) {
		int x, y;
		in >> p.x >> p.y;
		return in;
	}
};
// EndCodeSnip
 
int main() {
	int n;
	cin >> n;
	vector<Point> points(n);
	for (Point &point : points) { cin >> point; }
	points.push_back(points[0]);
	long long area = 0;
	for (int i = 0; i < n; i++) {
		area +=
		    (1LL * points[i].x * points[i + 1].y - 1LL * points[i].y * points[i + 1].x);
	}
	area = abs(area);
	long long boundary_points = 0;
	for (int i = 0; i < n; i++) {
		Point diff = points[i + 1] - points[i];
		int g = gcd(abs(diff.x), abs(diff.y));
		boundary_points += g;
	}
	long long interior_points = (area - boundary_points) / 2 + 1;
	cout << interior_points << ' ' << boundary_points;
}


from math import gcd
 
 
class Point:
	def __init__(self, x: int = 0, y: int = 0):
		self.x = x
		self.y = y
 
	def __sub__(self, other):
		return Point(self.x - other.x, self.y - other.y)
 
 
n = int(input())
points = []
 
for _ in range(n):
	x, y = map(int, input().split())
	points.append(Point(x, y))
 
points.append(points[0])
 
area = 0
for i in range(n):
	area += points[i].x * points[i + 1].y - points[i].y * points[i + 1].x
 
area = abs(area)
boundary_points = 0
 
for i in range(n):
	diff = points[i + 1] - points[i]
	g = gcd(abs(diff.x), abs(diff.y))
	boundary_points += g
 
interior_points = (area - boundary_points) // 2 + 1
 
print(interior_points, boundary_points)

Fuente	Nombre	Dificultad	Solución
YS	Sort Points by Argument	Fácil	Solución
Kattis	Segment Intersection	Fácil	Solución
Kattis	Segment Distance	Fácil	Solución
Kattis	Point in Polygon	Fácil	Solución
Kattis	Polygon Area	Fácil	Solución
LC	Max Points on a Line	Fácil	Solución
IOI	The Troublesome Frog	Normal	Solución
AC	Manhattan Multifocal Ellipse	Difícil	—

Ángulos

Hecho	Fuente	Nombre	Dificultad	Tags	Solución
	LC	Maximum Number of Visible Points	Normal	Geometry, Radians, Sliding Windows	en el módulo

Explicación

Trabajar con ángulos solo tiene sentido en el contexto de rectas y segmentos. Por lo tanto, consideremos los segmentos que conectan la posición inicial y cada punto: $(pos_x, pos_y)-(x, y)$ . Uno de esos segmentos está dentro del campo de visión si y solo si su pendiente es mayor que la cota inferior y menor que la cota superior. Como estamos trabajando con ángulos, convertiremos las pendientes a radianes.

Considerar $\alpha$ como el ángulo formado por una recta con el eje $\texttt{ox}$ . Entonces tenemos:

\texttt{slope}=\frac{\Delta y}{\Delta x}=\tg{\alpha} \\ \alpha=\arctg{\frac{\Delta y}{\Delta x}}

El movimiento del campo de visión se puede ver como una ventana deslizante aplicada sobre los ángulos ordenados de los puntos. El ángulo del campo de visión podría ser lo suficientemente grande como para ver puntos del comienzo del arreglo ordenado, así que el arreglo de ángulos debería duplicarse: arreglo cíclico.

Implementación

Complejidad temporal: $\mathcal{O}(N \log N)$

C++Python


class Solution {
  public:
	int visiblePoints(vector<vector<int>> &points, int angle, vector<int> &location) {
		int extra = 0;
		vector<double> angles;
		for (const vector<int> &p : points) {
			// Ignore points identical to location
			if (p == location) {
				extra++;
				continue;
			}
			// Take the arctg in radians
			angles.push_back(atan2(p[1] - location[1], p[0] - location[0]));
		}
 
		if (angles.empty()) { return extra; }
 
		// Sort angles
		sort(angles.begin(), angles.end());
		// Duplicate the array and add 2*PI to the angles
		for (int i = 0; i < (int)points.size(); i++) {
			angles.push_back(angles[i] + 2 * M_PI);
		}
 
		int ans = 0;
		double angle_radians = M_PI * angle / 180;
		// Sliding window
		for (int r = 0, l = 0; r < (int)angles.size(); r++) {
			// Pop all the points out of the field of view
			while (angles[r] - angles[l] > angle_radians) { l++; }
			ans = max(ans, r - l + 1);
		}
 
		return ans + extra;
	}
};


class Solution:
	def visiblePoints(
		self, points: List[List[int]], angle: int, location: List[int]
	) -> int:
		extra = 0
		angles = []
 
		for p in points:
			# Ignore points identical to location
			if p == location:
				extra += 1
				continue
 
			# Take the arctg in radians
			angles.append(atan2(p[1] - location[1], p[0] - location[0]))
 
		if not angles:
			return extra
 
		# Sort angles
		angles.sort()
 
		# Duplicate the array and add 2*PI to the angles
		angles += [a + 2 * pi for a in angles]
 
		ans = 0
		angle_radians = pi * angle / 180
 
		l = 0
		# Sliding window
		for r in range(len(angles)):
			# Pop all the points out of the field of view
			while angles[r] - angles[l] > angle_radians:
				l += 1
			ans = max(ans, r - l + 1)
 
		return ans + extra

Hecho	Fuente	Nombre	Dificultad	Tags	Solución
	AC	Laser Takahashi	Normal	Geometry, Sorting, Angles	—
	LC	Maximum Number of Darts Inside of a Circular Dartboard	Difícil		Solución

Problemas varios

Algunas olimpiadas europeas, como la CEOI, la Balkan OI y la Croatian OI, suelen tener muchos problemas de geometría. Estos problemas también suelen ser bastante difíciles, así que hay que buscar problemas ahí cuando se agoten los problemas para practicar.

Fuente	Nombre	Dificultad	Solución
CF	Cut Length	Difícil	Solución
Kattis	Max Collinear	Difícil	Solución
Kattis	Birthday Cake	Difícil	Solución