Dada una array arr[] de N puntos enteros distintos en el Plano 2D . La tarea es contar el número de Triángulos Rectángulos desde N puntos tales que la base o la perpendicular sea paralela al eje X o Y.
Ejemplos:
Entrada: arr[][] = {{4, 2}, {2, 1}, {1, 3}}
Salida: 0
Explicación:En la imagen de arriba no se forma un triángulo rectángulo.
Entrada: arr[][] = {{1, 2}, {2, 1}, {2, 2}, {2, 3}, {3, 2}}
Salida: 4
Explicación:En la imagen de arriba hay 4 triángulos rectángulos formados por los triángulos ACB, ACD, DCE, BCE .
Enfoque: La idea es almacenar el recuento de cada coordenada que tenga las mismas coordenadas X e Y respectivamente. Ahora atraviese cada uno de los puntos dados y la cuenta de un triángulo rectángulo formado por cada coordenada (X, Y) está dada por:
Recuento de triángulos rectángulos = (frecuencias de coordenadas X – 1) * (frecuencias de coordenadas Y – 1)
A continuación se muestran los pasos:
- Cree dos mapas para almacenar el recuento de puntos, uno por tener la misma coordenada X y otro por tener la misma coordenada Y.
- Para cada valor en el mapa de la coordenada x y en el mapa de la coordenada y, elija ese par de puntos como elementos de pivote y encuentre la frecuencia de ese elemento de pivote.
- Para cada elemento de pivote (por ejemplo, pivote ) en el paso anterior, el recuento de ángulos rectos viene dado por:
(m1[pivote].segundo-1)*(m2[pivote].segundo-1)
- De manera similar, calcule el triángulo rectángulo posible total para otros N puntos dados.
- Finalmente, suma todo el triángulo posible obtenido que es la respuesta final.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find the number of right // angled triangle that are formed from // given N points whose perpendicular or // base is parallel to X or Y axis int RightAngled(int a[][2], int n) { // To store the number of points // has same x or y coordinates unordered_map<int, int> xpoints; unordered_map<int, int> ypoints; for (int i = 0; i < n; i++) { xpoints[a[i][0]]++; ypoints[a[i][1]]++; } // Store the total count of triangle int count = 0; // Iterate to check for total number // of possible triangle for (int i = 0; i < n; i++) { if (xpoints[a[i][0]] >= 1 && ypoints[a[i][1]] >= 1) { // Add the count of triangles // formed count += (xpoints[a[i][0]] - 1) * (ypoints[a[i][1]] - 1); } } // Total possible triangle return count; } // Driver Code int main() { int N = 5; // Given N points int arr[][2] = { { 1, 2 }, { 2, 1 }, { 2, 2 }, { 2, 3 }, { 3, 2 } }; // Function Call cout << RightAngled(arr, N); return 0; }
Python3
# Python3 program for the above approach from collections import defaultdict # Function to find the number of right # angled triangle that are formed from # given N points whose perpendicular or # base is parallel to X or Y axis def RightAngled(a, n): # To store the number of points # has same x or y coordinates xpoints = defaultdict(lambda:0) ypoints = defaultdict(lambda:0) for i in range(n): xpoints[a[i][0]] += 1 ypoints[a[i][1]] += 1 # Store the total count of triangle count = 0 # Iterate to check for total number # of possible triangle for i in range(n): if (xpoints[a[i][0]] >= 1 and ypoints[a[i][1]] >= 1): # Add the count of triangles # formed count += ((xpoints[a[i][0]] - 1) * (ypoints[a[i][1]] - 1)) # Total possible triangle return count # Driver Code N = 5 # Given N points arr = [ [ 1, 2 ], [ 2, 1 ], [ 2, 2 ], [ 2, 3 ], [ 3, 2 ] ] # Function call print(RightAngled(arr, N)) # This code is contributed by Stuti Pathak
Java
// Java program for the above approach import java.util.*; class GFG{ // Function to find the number of right // angled triangle that are formed from // given N points whose perpendicular or // base is parallel to X or Y axis static int RightAngled(int a[][], int n) { // To store the number of points // has same x or y coordinates HashMap<Integer, Integer> xpoints = new HashMap<Integer, Integer>(); HashMap<Integer, Integer> ypoints = new HashMap<Integer, Integer>(); for (int i = 0; i < n; i++) { if(xpoints.containsKey(a[i][0])) { xpoints.put(a[i][0], xpoints.get(a[i][0]) + 1); } else { xpoints.put(a[i][0], 1); } if(ypoints.containsKey(a[i][1])) { ypoints.put(a[i][1], ypoints.get(a[i][1]) + 1); } else { ypoints.put(a[i][1], 1); } } // Store the total count of triangle int count = 0; // Iterate to check for total number // of possible triangle for (int i = 0; i < n; i++) { if (xpoints.get(a[i][0]) >= 1 && ypoints.get(a[i][1]) >= 1) { // Add the count of triangles // formed count += (xpoints.get(a[i][0]) - 1) * (ypoints.get(a[i][1]) - 1); } } // Total possible triangle return count; } // Driver Code public static void main(String[] args) { int N = 5; // Given N points int arr[][] = { { 1, 2 }, { 2, 1 }, { 2, 2 }, { 2, 3 }, { 3, 2 } }; // Function Call System.out.print(RightAngled(arr, N)); } } // This code is contributed by Rajput-Ji
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG{ // Function to find the number of right // angled triangle that are formed from // given N points whose perpendicular or // base is parallel to X or Y axis static int RightAngled(int[, ] a, int n) { // To store the number of points // has same x or y coordinates Dictionary<int, int> xpoints = new Dictionary<int, int>(); Dictionary<int, int> ypoints = new Dictionary<int, int>(); for (int i = 0; i < n; i++) { if (xpoints.ContainsKey(a[i, 0])) { xpoints[a[i, 0]] = xpoints[a[i, 0]] + 1; } else { xpoints.Add(a[i, 0], 1); } if (ypoints.ContainsKey(a[i, 1])) { ypoints[a[i, 1]] = ypoints[a[i, 1]] + 1; } else { ypoints.Add(a[i, 1], 1); } } // Store the total count of triangle int count = 0; // Iterate to check for total number // of possible triangle for (int i = 0; i < n; i++) { if (xpoints[a[i, 0]] >= 1 && ypoints[a[i, 1]] >= 1) { // Add the count of triangles // formed count += (xpoints[a[i, 0]] - 1) * (ypoints[a[i, 1]] - 1); } } // Total possible triangle return count; } // Driver Code public static void Main(String[] args) { int N = 5; // Given N points int[, ] arr = {{1, 2}, {2, 1}, {2, 2}, {2, 3}, {3, 2}}; // Function Call Console.Write(RightAngled(arr, N)); } } // This code is contributed by Rajput-Ji
Javascript
<script> // JavaScript program for the above approach // Function to find the number of right // angled triangle that are formed from // given N points whose perpendicular or // base is parallel to X or Y axis function RightAngled(a, n) { // To store the number of points // has same x or y coordinates var xpoints = {}; var ypoints = {}; for (var i = 0; i < n; i++) { if (xpoints.hasOwnProperty(a[i][0])) { xpoints[a[i][0]] = xpoints[a[i][0]] + 1; } else { xpoints[a[i][0]] = 1; } if (ypoints.hasOwnProperty(a[i][1])) { ypoints[a[i][1]] = ypoints[a[i][1]] + 1; } else { ypoints[a[i][1]] = 1; } } // Store the total count of triangle var count = 0; // Iterate to check for total number // of possible triangle for (var i = 0; i < n; i++) { if (xpoints[a[i][0]] >= 1 && ypoints[a[i][1]] >= 1) { // Add the count of triangles // formed count += (xpoints[a[i][0]] - 1) * (ypoints[a[i][1]] - 1); } } // Total possible triangle return count; } // Driver Code var N = 5; // Given N points var arr = [ [1, 2], [2, 1], [2, 2], [2, 3], [3, 2], ]; // Function Call document.write(RightAngled(arr, N)); </script>
4
Complejidad de tiempo: O(N+N), es decir, O(N)
Espacio auxiliar: O(N+N), es decir, O(N)