De ninguna manera es una lista completa, y tampoco es una clasificación verdaderamente correcta o completa. Solo trataré de mencionar un montón de problemas que tienden a ocurrir, y los incluiré en algunas categorías para que sea más legible.
Primero, casi todos los problemas de geometría en los concursos de programación son sobre geometría euclidiana bidimensional. Los problemas tridimensionales (o más) son raros. Parte de la razón es su dificultad: tienden a ser fáciles (y solo hay algunos de esos), o casi imposiblemente difíciles.
Otra razón es la maldición de la dimensionalidad: para los datos de muchas dimensiones, a menudo la mejor solución es la fuerza bruta. Esto se debe a que la complejidad temporal de un algoritmo a menudo crece rápidamente con el número de dimensiones. Ejemplo: para algunos problemas en los que la entrada es un conjunto de [matemática] n [/ matemática] puntos en [matemática] d [/ matemática] -dimensional hay algoritmos con complejidades temporales como [matemática] O (n2 ^ d) [ / math] o [math] O (n \ log ^ dn) [/ math]. En los concursos de programación, generalmente hay que usar conjuntos de datos de entrada que se pueden resolver en unos segundos. Y cualquier cosa que el algoritmo eficiente pueda resolver en unos segundos también puede resolverse mediante una solución directa [matemática] O (n ^ 2) [/ matemática] o [matemática] O (n ^ 2d) [/ matemática] que intenta rápidamente todo posibilidades El algoritmo asintóticamente mejor (en términos de [matemática] n [/ matemática]) solo se vuelve mejor para valores imprácticamente grandes de [matemática] n [/ matemática].
- ¿Debo aprender algoritmos y estructuras de datos de cada lenguaje de programación?
- ¿Debería seleccionar siempre el algoritmo con el menor orden de complejidad?
- ¿Cómo se siente Bram Cohen al haber creado accidentalmente un algoritmo para el cifrado totalmente homomórfico?
- ¿Cuál es el intercambio de espacio temporal en las estructuras de datos?
- ¿Existe un libro o sitio web que describa los problemas y luego le solicite la estructura de datos / algoritmos más apropiados necesarios para resolver el problema?
Dentro de la geometría 2D, existe una clase popular de problemas que se puede resolver exactamente: las entradas son puntos y estructuras lineales (como segmentos, líneas, cuadrados, etc.), las coordenadas de todos los puntos son enteros y la pregunta que se nos permite hacer todos los cálculos en enteros. Para tales problemas, esta suele ser una buena idea, ya que evita problemas de precisión. Ejemplos notables:
- conceptos básicos de ubicación relativa, como la colinealidad / dirección de rotación para puntos y vectores
- casco convexo y su doble: la envoltura de líneas superior / inferior
- muchos algoritmos de barrido, por ejemplo, área y perímetro de la unión de ejes-rectángulos paralelos
- Algoritmos elementales relacionados con polígonos: pruebas de punto en polígono (ya sea una vez, o preprocesamiento + muchas consultas), área de polígono, triangulación de polígono
Además, a veces podemos calcular todo exactamente, y solo usamos números de punto flotante al final para calcular el resultado:
- centro de masa de un polígono
- varias distancias de objetos lineales: punto-punto, punto-línea, punto-segmento, segmento-segmento, par más cercano entre n puntos, distancia entre dos polígonos
(Tenga en cuenta que si todos los puntos tienen coordenadas enteras, los cuadrados de sus distancias son todos enteros).
En otros problemas aún podemos calcular todo exactamente, pero ya tenemos que lidiar con números racionales. Para estos problemas, a menudo es más fácil usar números de punto flotante en sus cálculos e incluir medidas apropiadas para lidiar con imprecisiones numéricas. Ejemplos:
- Intersecciones de objetos lineales: dos líneas, dos segmentos de línea, n segmentos de línea, dos polígonos convexos, polígonos generales, etc.
El objeto no lineal más común que aparece en los problemas del concurso de programación es el círculo. Los puntos definidos usando círculos no tienen que tener coordenadas racionales, por lo que, por lo general, la única forma razonable de resolver tales problemas es usar variables de punto flotante y tratar los errores de redondeo. (Técnicamente, las coordenadas son a menudo números algebraicos y a veces es posible hacer el cálculo exactamente representándolos usando sus polinomios mínimos, pero esto es demasiado doloroso y tedioso para hacer en un concurso. Simplemente ignore la oración anterior 🙂)
Ejemplos:
- intersecciones círculo-línea y círculo-círculo
- tangentes de punto y círculo y círculo y círculo
- áreas de sectores circulares y segmentos circulares y objetos más complicados que se pueden componer usando esos: área de intersección para un círculo y un objeto lineal; También área de intersección para dos círculos
- Una excepción notable: la longitud convexa del casco para n círculos idénticos se puede calcular sorprendentemente fácilmente 🙂
Luego está el conjunto de tareas relacionadas con la localidad que son bastante difíciles de implementar de manera eficiente, y todas más o menos equivalentes: diagrama de Voronoi, triangulación de Delaunay, árbol de expansión mínima euclidiana, vecino más cercano para cada uno de los n puntos dados, etc. .
Y muchos otros temas. El libro de de Berg et al. es una de las referencias de geometría computacional estándar. Consulte su tabla de contenido para obtener más información: Geometría computacional, Algoritmos y Aplicaciones
La pregunta también se refiere a las estructuras de datos. Personalmente, no creo que alguna vez haya usado algo demasiado elegante en un concurso, solo su BST equilibrado estándar para almacenar cosas a las que necesita acceder rápidamente, por ejemplo, eventos y / o estado de línea de barrido durante el barrido.
