Curso de colisión | TCS Mock Vita 2020

Descripción del problema

En una calle muy transitada, pasan varios autos. Se ejecuta una simulación para ver qué sucede si fallan los frenos de todos los automóviles en la carretera. La única forma de que estén a salvo es si no chocan y pasan uno al lado del otro. El objetivo es identificar si alguno de los autos dados chocaría o pasaría de manera segura alrededor de una rotonda. Piense en esto como un punto de referencia O ( Origen con coordenadas (0, 0) ), pero en lugar de rodearlo, los automóviles lo atraviesan.

Considerando que cada automóvil se mueve en línea recta hacia el origen con velocidad uniforme individual. Los automóviles seguirán viajando en la misma línea recta incluso después de cruzar el origen. Calcula el número de colisiones que ocurrirán en tal escenario.

Nota: Calcula las colisiones solo en el origen. Ignora las otras colisiones. Suponga que cada automóvil continúa en su camino respectivo incluso después de la colisión sin cambiar de dirección o velocidad por una distancia infinita.

Dada una array car[] que contiene las coordenadas y su velocidad para cada elemento. Encuentre el número total de colisiones en el origen.

Ejemplo:

Entrada: carro[] ={(5 12 1), (16 63 5), (-10 24 2), (7 24 2), (-24 7 2)}
Salida: 4
Explicación:
Sean los 5 carros A , B, C, D y E respectivamente.
4 Las colisiones son las siguientes:
A y B, A y C, B y C, D y E

Enfoque: La idea es encontrar el número de autos que chocan en el origen. Nos dan la posición de coordenadas de los autos, a partir de la cual podemos encontrar la distancia de los autos desde el origen.

Sean x, y la posición de un automóvil, entonces la distancia desde el origen será:

Dividir esta distancia por la velocidad nos dará el tiempo en que un automóvil está presente en el origen. Entonces, si hay ‘N’ automóviles presentes en el origen en algún instante de tiempo, las colisiones totales serán 

Agregar todas las colisiones en una instancia diferente de tiempo dará la respuesta requerida.

A continuación se muestra la implementación del enfoque anterior:

// C++ implementation to find the
// collision at the origin
  
#include <bits/stdc++.h>
using namespace std;
  
// Structure to store the
// co-ordinates of car and speed
struct Car {
    long long x;
    long long y;
    long long v;
};
  
// Function to find the co-ordinates
// of the car and speed
long long solve(long long c,
                vector<Car>& arr)
{
    map<long long, long long> freq;
  
    long sum = 0;
    for (long long i = 0; i < c; i++) {
        long long x = arr[i].x,
                  y = arr[i].y,
                  v = arr[i].v;
        long long dist_square
            = (x * x) + (y * y);
        long long time_square
            = dist_square / (v * v);
        freq[time_square]++;
    }
  
    // Loop to iterate over the
    // frequency of the elements
    for (auto it = freq.begin();
         it != freq.end(); it++) {
        long long f = it->second;
        if (f <= 0)
            continue;
  
        sum += (f * (f - 1)) / 2;
    }
  
    return sum;
}
  
// Driver Code
int main()
{
    long long c = 5;
  
    vector<Car> arr;
  
    Car tmp;
    tmp.x = 5;
    tmp.y = 12;
    tmp.v = 1;
    arr.push_back(tmp);
  
    tmp.x = 16;
    tmp.y = 63;
    tmp.v = 5;
    arr.push_back(tmp);
  
    tmp.x = -10;
    tmp.y = 24;
    tmp.v = 2;
    arr.push_back(tmp);
  
    tmp.x = 7;
    tmp.y = 24;
    tmp.v = 2;
    arr.push_back(tmp);
  
    tmp.x = -24;
    tmp.y = 7;
    tmp.v = 2;
    arr.push_back(tmp);
  
    cout << solve(c, arr);
  
    return 0;
}

4