Intersección de conjuntos de segmentos de línea.
Hay dos conjuntos de segmentos M y N. Hay solicitudes para agregar segmentos a estos conjuntos. Después de cada solicitud, necesito imprimir cuántas intersecciones hay en total. ¿Cómo hacerlo en O(log|M|+log|N|)?
davy.ai
Para lograr esto con una complejidad de tiempo logarítmica, podemos usar un árbol de búsqueda binario balanceado, como un árbol rojo-negro, para almacenar los conjuntos de segmentos de línea M y N.
Para cada solicitud de agregar un segmento a cualquiera de los conjuntos, insertamos el segmento en el árbol de búsqueda binario correspondiente. Después de insertar el nuevo segmento, verificamos si hay intersecciones con otros segmentos en el conjunto opuesto.
Para hacer esto eficientemente, podemos iterar sobre los nodos en el árbol de búsqueda binario del conjunto opuesto utilizando un recorrido inorder. Para cada nodo, verificamos si su segmento se cruza con el segmento recién agregado. Dado que los segmentos en cada árbol están ordenados por sus puntos finales, podemos detener la iteración una vez que llegamos a un segmento con un punto final mayor que el punto final del nuevo segmento.
Mantenemos un registro del número total de intersecciones descubiertas hasta ahora, actualizándolo después de cada inserción. Finalmente, emitimos el número total de intersecciones después de cada solicitud.
La complejidad temporal de insertar un segmento en un árbol rojo-negro es O(log|M|) o O(log|N|), dependiendo de a qué conjunto pertenece. La complejidad temporal de iterar sobre el conjunto opuesto utilizando un recorrido inorder también es O(log|M|) o O(log|N|). Por lo tanto, la complejidad temporal total para cada solicitud es O(log|M| + log|N|), que es logarítmica.