Miscellany

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <climits>
 
using namespace std;
 
struct Balle {
        float vitesse;
        float position;
};
 
struct Scenario {
        std::vector<Balle> balles;
       
        int trackedBall_i;     
        int temps;     
};

int GetNextIntersection(vector<Balle>& balles, int currBallIndex, float& time, float maxTime)
{
	const float VERY_LONG_TIME = 1000000;
	float closestCollision = VERY_LONG_TIME;
	int closestCollisionNumber;

	Balle* currBall = &balles[currBallIndex];

	for (unsigned int i = 0; i < balles.size(); i++)
	{
		if (i == currBallIndex)
		{
			continue;
		}

		// If the trajectories are //, skip to prevent division by 0
		if (balles[i].vitesse == currBall->vitesse)
		{
			continue;
		}

		float collisionTime = (balles[i].position - currBall->position) /
							  (currBall->vitesse - balles[i].vitesse);

		// If the collision is backward in time, forget this.
		if (collisionTime < time)
		{
			continue;
		}

		// If the delta is smaller than what we have right now, take this collision
		if ((collisionTime - time) < closestCollision)
		{
			closestCollision = collisionTime - time;
			closestCollisionNumber = i;
		}
	}

	// If the collision happens further than the time limit. Notify
	// so that we can calculate the final position
	if ((closestCollision + time) > maxTime || closestCollision == VERY_LONG_TIME)
	{
		return -1;
	}

	time += closestCollision + 0.01; // Small delta
	return closestCollisionNumber;
}

void solve(Scenario& s)
{
	int currBall = s.trackedBall_i - 1;
	float maxTime = s.temps;
	float currTime = 0;

	while (currTime < maxTime)
	{
		// If the ball is in the pocket. Calculate the position right now
		if (s.balles[currBall].position == 100.0 || s.balles[currBall].position == 0.0)
		{
			break;
		}

		int result = GetNextIntersection(s.balles, currBall, currTime, maxTime);

		if (result == -1)
		{
			break;
		}
		else
		{
			currBall = result;
		}
	}

	// Calculate the ending position
	float position = s.balles[currBall].position + s.balles[currBall].vitesse * maxTime;
	cout << (int)position;
}

int main() {
        int n;
       
        cin >> n;
       
        for (int i = 0; i < n; i++) {
                Scenario scenario;

                int nbBalles;
               
                cin >> nbBalles;
               
                for (int j = 0; j < nbBalles; j++) {
                        Balle balle;
                       
                        cin >> balle.position >> balle.vitesse;
                        if(balle.position >= 100 || balle.position <= 0)
                                balle.vitesse = 0;
                        scenario.balles.push_back(balle);                      
                }
               
                cin >> scenario.trackedBall_i >> scenario.temps;

				// Put pocket balls to make sure we will intersect with the pockets
				Balle pocket;
				pocket.vitesse = 0;
				pocket.position = 0;
				scenario.balles.push_back(pocket);
				pocket.position = 100;
				scenario.balles.push_back(pocket);

                solve(scenario);
                if (i != (n-1))
				{
					cout << endl;
				}
        }
       
        return 0;
}