Si hay un punto N en una gráfica cartesiana, ¿cómo calculo cuántos triángulos rectángulos se pueden formar?

Answer 1

Verifica cada punto, si es una esquina derecha de un triángulo. Llamaré a ese punto fijo O. Para hacerlo, clasifique todos los demás puntos por ángulo desde este punto (esto se puede hacer sin funciones de trigonometría; solo verifique un producto de punto de los vectores OA y OB, para verificar si el punto B debería ser posterior que el punto A. También algunos trucos adicionales para verificar en qué cuadrantes pertenecen los puntos). Este tipo se puede hacer en n log n time.
Luego debe usar el enfoque de “dos iteradores”: un iterador apuntará al primer punto inicialmente. El segundo iterador siempre apuntará a un primer punto, que da no menos de un ángulo recto con ese primer punto. Este punto es el único candidato que puede hacer que el ángulo AOB sea recto (A apunta al primer iterador, B apunta al segundo iterador). Es muy simple, solo inicialice ambos iteradores en el primer punto de una lista ordenada, y ellos moverán el segundo iterador, mientras que el producto escalar de los vectores OA y OB es positivo.
Luego, mueves el primer iterador paso a paso. El segundo iterador debe ajustarse y puede moverse varios pasos a la vez. Justo como antes. Pero siempre avanzará. Por lo tanto, estos iteradores se moverán no más de 2n veces juntos.
Cada vez que el segundo iterador deja de moverse, apunta a un primer punto, dando un ángulo de al menos 90 grados con un primer punto (mirando desde el punto O). Tenga en cuenta que este ángulo se cuenta en sentido antihorario y puede ser superior a 180 grados. Debe verificar si estos 2 puntos dan un ángulo recto. Si es así, encontraste tu triángulo. Si el ángulo es mayor de 90, entonces no hay un triángulo que involucre el punto en el primer iterador, muévalo al siguiente punto.
El procedimiento de clasificación e iteración se repite para todos los n puntos como origen.
Así que aplicamos fuerza bruta a todos los pares de puntos y verificamos si existen algunos puntos calculados en un conjunto dado usando la tabla hash. Hay O (N2) pares de puntos y la búsqueda en la tabla es muy rápida.

Answer 2

¿Podría primero mapear cada coordenada xy cada coordenada y a una lista de puntos que contienen esa coordenada x o coordenada y? Esto llevaría tiempo O (N) simplemente iterando a través de la lista de puntos y mapeando su coordenada xy su coordenada y. En cierto sentido, estás haciendo un seguimiento de lo que has “visto”. Y luego, para cada punto, vea si existe otro punto que tenga la misma coordenada xy otro punto que tenga la misma coordenada y que usted. ¿Esto requeriría consultar el mapa hash que es O (1) suponiendo que las colisiones se manejan de manera inteligente? ¿Y entonces estás haciendo 2 barridos lineales?