Platino
Consultas por rangos
Árboles
- Elevación binaria
- Ancestro común más bajo (LCA) - O(sqrt(N)) y O(log N) con preprocesamiento O(N)
- Ancestro común más bajo (LCA) - Binary Lifting (elevación binaria)
- Ancestro común más bajo - algoritmo de Farach-Colton y Bender
- Ancestro común más bajo - algoritmo offline de Tarjan
- Resolver RMQ (consulta de mínimo en un rango) encontrando el LCA (ancestro común más bajo)
- Fusión small-to-large
- Descomposición Heavy-Light
- Descomposición Heavy-Light
- Pintar las aristas del árbol
- Descomposición por centroide
- Descomposición por centroide
- Árbol virtual
- Árbol de reconstrucción de Kruskal
Geometría
- Primitivas de geometría
- Geometría básica
- Área orientada de un triángulo
- Punto de intersección de rectas
- Encontrar la ecuación de una recta para un segmento
- Encontrar la intersección de dos segmentos
- Comprobar si dos segmentos se intersectan
- Intersección círculo-recta
- Intersección círculo-círculo
- Encontrar las tangentes comunes a dos círculos
- Distancia de Manhattan
- Encontrar el área de un polígono simple en O(N)
- Teorema de Pick
- Puntos de retículo dentro de un polígono que no es de retículo
- Línea de barrido
- Buscar un par de segmentos que se intersectan
- Longitud de la unión de segmentos
- Localización de puntos en O(log n)
- Encontrar el par de puntos más cercano
- Descomposición vertical
- Envolvente convexa
- Construcción de la envolvente convexa
- Comprobar si un punto pertenece al polígono convexo en O(log N)
- Suma de Minkowski de polígonos convexos
- Círculo mínimo envolvente
- Intersección de semiplanos
- Triangulación de Delaunay y diagrama de Voronoi
- Truco de la envolvente convexa
- Truco de la envolvente convexa (CHT) y Árbol de Li Chao
Temas variados
- Principio de inclusión-exclusión
- El principio de inclusión-exclusión
- Exponenciación de matrices
- Números de Fibonacci
- Número de caminos de longitud fija / Caminos más cortos de longitud fija
- (Opcional) Bitsets
- Divide y vencerás - DP
- DP de divide y vencerás
- DP de suma sobre subconjuntos
- Enumeración de submáscaras