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>
Producción:
4
Complejidad de tiempo: O(N+N), es decir, O(N)
Espacio auxiliar: O(N+N), es decir, O(N)