Dada una array arr[][] de tamaño N * 3 tal que cada fila consta de 3 propiedades que definen un elemento, es decir (coordenada x, coordenada y, velocidad) , y dos enteros X e Y , la tarea es contar el número de posibles pares de colisiones en el punto (X, Y) , si cada elemento de la array dada se mueve en línea recta hacia el punto dado (X, Y) con sus respectivas velocidades.
Ejemplos:
Entrada: arr[] = [ [5, 12, 1], [16, 63, 5], [-10, 24, 2], [7, 24, 2], [-24, 7, 2] ], X = 0, Y = 0
Salida: 4
Explicación:
Las colisiones posibles son entre el siguiente par de elementos: (arr[0], arr[1]), (arr[0], arr[2]), (arr[1 ], arr[2]) y (arr[3], arr[4])
Por lo tanto, el total de colisiones es 4.
Entrada: arr[] = [ [1, 42, 9] ], X = 1, Y = 1
Salida : 0
Explicación:
Dado que hay un solo punto presente, no habrá colisiones.
Por lo tanto, las colisiones totales son 0.
Enfoque: La idea es simplemente encontrar el tiempo en el que cada punto llegará al punto dado (X, Y). Si dos puntos llegan al origen al mismo tiempo, seguramente chocarán. Ahora, para calcular el tiempo que tarda cada punto, haga lo siguiente:
Para un punto dado (x, y) y velocidad S
La distancia D viene dada por:
D = = √ ((x2 – x1) 2 + (y2 – y1) 2 ) = √ ((x) 2 + (y) 2 )
Tiempo = Distancia/Velocidad, elevando al cuadrado en ambos lados para eliminar la raíz de la distancia,
Tiempo 2 = Distancia 2 /Velocidad 2
Después de calcular el tiempo 2 para cada punto, simplemente verifica cuáles de ellos son iguales y cuenta el número de colisiones.
A continuación se muestran los pasos:
- Recorre la array arr[] .
- Cree una nueva array Time[] y para cada punto, calcule el tiempo y agregue a esta array y ordénela.
- Traverse Time[] y cuente el número de elementos que llegan al punto dado al mismo tiempo, usando el conteo calcule el número de colisiones en ese momento.
- Finalmente, devuelva el recuento total de colisiones.
A continuación se muestra la implementación del enfoque anterior:
C++14
// C++14 program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the count of
// possible pairs of collisions
int solve(vector<vector<int>> &D, int N,
int X, int Y)
{
// Stores the time at which
// points reach the origin
vector<double> T;
// Calculate time for each point
for(int i = 0; i < N; i++)
{
int x = D[i][0];
int y = D[i][1];
double speed = D[i][2];
double time = ((x * x - X * X) +
(y * y - Y * Y)) /
(speed * speed);
T.push_back(time);
}
// Sort the times
sort(T.begin(), T.end());
int i = 0;
int total = 0;
// Counting total collisions
while (i < T.size() - 1)
{
// Count of elements arriving at
// a given point at the same time
int count = 1;
while (i < T.size() - 1 and
T[i] == T[i + 1])
{
count += 1;
i += 1;
}
total += (count * (count - 1)) / 2;
i += 1;
}
return total;
}
// Driver Code
int main()
{
int N = 5;
// Given set of points with speed
vector<vector<int>> D = { { 5, 12, 1 },
{ 16, 63, 5 },
{ -10, 24, 2 },
{ 7, 24, 2 },
{ -24, 7, 2 } };
int X = 0, Y = 0;
// Function call
cout << (solve(D, N, X, Y));
return 0;
}
// This code is contributed by mohit kumar 29
Java
// Java program to implement
// the above approach
import java.util.*;
import java.lang.*;
class GFG{
// Function to find the count of
// possible pairs of collisions
static double solve(int[][] D, int N,
int X, int Y)
{
// Stores the time at which
// points reach the origin
ArrayList<Double> T = new ArrayList<>();
// Calculate time for each point
for(int i = 0; i < N; i++)
{
int x = D[i][0];
int y = D[i][1];
double speed = D[i][2];
double time = ((x * x - X * X) +
(y * y - Y * Y)) /
(speed * speed);
T.add(time);
}
// Sort the times
Collections.sort(T);
int i = 0;
int total = 0;
// Counting total collisions
while (i < (T.size() - 1))
{
// Count of elements arriving at
// a given point at the same time
int count = 1;
while ((i < (T.size() - 1)) &&
(Double.compare(T.get(i),
T.get(i + 1)) == 0))
{
count += 1;
i += 1;
}
total += (count * (count - 1)) / 2;
i += 1;
}
return total;
}
// Driver Code
public static void main (String[] args)
{
int arr[] = { 1, 2, 3, 4, 5 };
int N = 5;
// Given set of points with speed
int[][] D = { { 5, 12, 1 },
{ 16, 63, 5 },
{ -10, 24, 2 },
{ 7, 24, 2 },
{ -24, 7, 2 } };
int X = 0, Y = 0;
// Function call
System.out.println(solve(D, N, X, Y));
}
}
// This code is contributed by offbeat
Python3
# Python3 Program to implement # the above approach # Function to find the count of # possible pairs of collisions def solve(D, N, X, Y): # Stores the time at which # points reach the origin T = [] # Calculate time for each point for i in range(N): x = D[i][0] y = D[i][1] speed = D[i][2] time = ((x * x - X * X) + (y * y - Y * Y)) / (speed * speed) T.append(time) # Sort the times T.sort() i = 0 total = 0 # Counting total collisions while i<len(T)-1: # Count of elements arriving at # a given point at the same time count = 1 while i<len(T)-1 and T[i] == T[i + 1]: count += 1 i+= 1 total+= (count*(count-1))/2 i+= 1 return total # Driver Code N = 5 # Given set of points with speed D = [[5, 12, 1], [16, 63, 5], \ [-10, 24, 2], [7, 24, 2], \ [-24, 7, 2]] X = 0 Y = 0 # Function Call print(solve(D, N, X, Y))
C#
// C# program to implement
// the above approach
using System;
using System.Collections;
class GFG{
// Function to find the count of
// possible pairs of collisions
static double solve(int[, ] D, int N,
int X, int Y)
{
// Stores the time at which
// points reach the origin
ArrayList T = new ArrayList();
// Calculate time for each point
for(int i = 0; i < N; i++)
{
int x = D[i, 0];
int y = D[i, 1];
double speed = D[i, 2];
double time = ((x * x - X * X) +
(y * y - Y * Y)) /
(speed * speed);
T.Add(time);
}
// Sort the times
T.Sort();
int j = 0;
int total = 0;
// Counting total collisions
while (j < (T.Count - 1))
{
// Count of elements arriving at
// a given point at the same time
int count = 1;
while ((j < (T.Count - 1)) &&
(Convert.ToDouble(T[j]).CompareTo(
Convert.ToDouble(T[j + 1])) == 0))
{
count += 1;
j += 1;
}
total += (count * (count - 1)) / 2;
j += 1;
}
return total;
}
// Driver Code
public static void Main (String[] args)
{
int N = 5;
// Given set of points with speed
int [,] D = new int [,] { { 5, 12, 1 },
{ 16, 63, 5 },
{ -10, 24, 2 },
{ 7, 24, 2 },
{ -24, 7, 2 } };
int X = 0, Y = 0;
// Function call
Console.WriteLine(solve(D, N, X, Y));
}
}
// This code is contributed by jana_sayantan
Javascript
<script>
// JavaScript program to implement
// the above approach
// Function to find the count of
// possible pairs of collisions
function solve(D,N,X,Y)
{
// Stores the time at which
// points reach the origin
let T = [];
// Calculate time for each point
for(let i = 0; i < N; i++)
{
let x = D[i][0];
let y = D[i][1];
let speed = D[i][2];
let time = ((x * x - X * X) +
(y * y - Y * Y)) /
(speed * speed);
T.push(time);
}
// Sort the times
T.sort(function(a,b){return a-b;});
let i = 0;
let total = 0;
// Counting total collisions
while (i < (T.length - 1))
{
// Count of elements arriving at
// a given point at the same time
let count = 1;
while ((i < (T.length - 1)) &&
(T[i]==T[i+1]))
{
count += 1;
i += 1;
}
total += (count * (count - 1)) / 2;
i += 1;
}
return total;
}
// Driver Code
let arr=[1, 2, 3, 4, 5];
let N = 5;
// Given set of points with speed
let D = [[5, 12, 1], [16, 63, 5],
[-10, 24, 2], [7, 24, 2],
[-24, 7, 2]];
let X = 0, Y = 0;
// Function call
document.write(solve(D, N, X, Y).toFixed(1));
// This code is contributed by patel2127
</script>
4.0
Complejidad temporal: O(N log N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por bhanumeghraj y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA