Para los rectángulos, mi idea sería hacer una compresión de coordenadas y luego usar alguna estructura de datos como un árbol de rango 2D.
Pero para los círculos las cosas se vuelven más complicadas. Una idea que me viene a la mente es imaginar los círculos como rectángulos y usar la misma idea que antes pero, en lugar de simplemente “aceptar”, uno necesita verificar para cada uno de los círculos candidatos que el punto reside en él. Pero, desafortunadamente, esta solución puede ser lineal para cada punto.
Entonces, intentemos otro enfoque (suponiendo que podamos responder “sin conexión”):
En lugar de preguntar cuántos círculos contienen un punto, hacemos lo contrario. Es decir, para cada círculo actualizamos la respuesta de cada punto dentro de ese círculo.
Una implementación simple de esta idea no resultará en una mejor complejidad que antes, pero si usamos alguna estructura de datos como un Árbol de Rango 2D o un Quadtree y … “propagación diferida”, podemos lograr una mejor complejidad. (Necesita una implementación muy cuidadosa)
- ¿Es posible hackear usando el lenguaje de programación C?
- ¿Cuál es la optimización de un conjunto de antenas?
- ¿Es una persona inteligente debido a los 'algoritmos' que usa su cerebro? Si es así, ¿alguien podría copiar ese 'algoritmo' para ser igualmente inteligente?
- ¿Cuál es el mecanismo fundamental detrás de los generadores de números aleatorios?
- Cómo habilitar la compresión gzip
¡Espero que haya sido útil!
