Data Modelling & AI Data Structure & Algorithm

Count of collisions at a point (X, Y)

23 June 2025

0

Given a matrix arr[][] of size N * 3 such that each row consists of 3 properties defining an element, i.e. (x-coordinate, y-coordinate, speed), and two integers X and Y, the task is to count the number of possible pairs of collisions at the point (X, Y), if every element in the given array is moving in a straight line towards the given point (X, Y) with their respective speeds.
Examples:

Input: arr[] = [ [5, 12, 1], [16, 63, 5], [-10, 24, 2], [7, 24, 2], [-24, 7, 2] ], X = 0, Y = 0
Output: 4
Explanation:
Possible collisions are between the following pair of elements: (arr[0], arr[1]), (arr[0], arr[2]), (arr[1], arr[2]) and (arr[3], arr[4])
Hence, total collisions are 4.
Input: arr[] = [ [1, 42, 9] ], X = 1, Y = 1
Output: 0
Explanation:
Since a single point is present, there will be no collisions.
Hence, total collisions are 0.

Approach: The idea is to simply find the time at which every point will reach the given point (X, Y). If two points reach the origin at the same time, then they will surely collide. Now, to calculate the time taken by each point do the following:

For a given point (x, y) and speed S
Distance D is given by:
D = = ? ((x2 – x1)² + (y2 – y1)²) = ? ((x)² + (y)²)
Time = Distance/Speed, squaring on both sides to eliminate root from distance,
Time² = Distance²/Speed²

After calculating time² for each point, simply check which of them are same and count the number of collisions.
Below are the steps:

Traverse the array arr[].
Create a new array Time[] and for each point, calculate time and append to this array and sort it.
Traverse Time[] and count the number of elements which arrive the given point at the same time, using the count calculate the number of collisions at that time.
Finally, return the total count of collisions.

Below is the implementation of the above approach:

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>

Output:

4.0

Time Complexity: O(N log N)
Auxiliary Space: O(N) because using extra space for vector T

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!

Count of collisions at a point (X, Y)

C++14

Java

Python3

C#

Javascript

LangExtract + Milvus: A Practical Guide to Building a Hybrid Document Processing and Search System

Stop Your AI Assistant from Writing Outdated Code with Milvus SDK Code Helper

A Practical Guide for Choosing the Right Vector Database for Your AI Applications

LEAVE A REPLY Cancel reply

Most Popular

Nothing’s next earbuds will get back on a familiar track

Timekettle’s new Interpreter earbuds aim tobreak down languages barriers in real time

At $70 off, the Galaxy Tab S10 FE+ just dropped to its best price ever

NBA 2K26 publisher teases its first new college basketball video game since 2007

EDITOR PICKS

Nothing’s next earbuds will get back on a familiar track

Timekettle’s new Interpreter earbuds aim tobreak down languages barriers in real time

At $70 off, the Galaxy Tab S10 FE+ just dropped to its best price ever

POPULAR POSTS

Nothing’s next earbuds will get back on a familiar track

Timekettle’s new Interpreter earbuds aim tobreak down languages barriers in real time

At $70 off, the Galaxy Tab S10 FE+ just dropped to its best price ever

POPULAR CATEGORY

ABOUT US

FOLLOW US