TopCoder problem "ParticleCollision" used in SRM 401 (Division I Level Two)



Problem Statement

    

Particles (which can be considered points in 3D-space for the purposes of the problem) can move in an electro-magnetic field. If a particle is charged, its trajectory can be described as spiral, and if it is uncharged, it is just a straight line. Given two particles (one charged and one uncharged) it should be determined whether they can possibly collide or not. Two particles can possibly collide if and only if their trajectories intersect.

Some steps have already been made by the physicist to simplify the problem, so the coordinates of the charged particle are represented as follows:

x1 = cos(PI * t)

y1 = sin(PI * t)

z1 = t

and for the uncharged particle:

x2 = vx * t + x0

y2 = vy * t + y0

z2 = vz * t + z0

Here t is a parameter which can be chosen arbitrarily and independently for both trajectories.

Your method will be given 6 integers - vx, vy, vz, x0, y0 and z0, describing the trajectory of the uncharged particle. It should determine whether the two given trajectories intersect or not. If they do, it should return a double[] containing exactly 3 elements x, y and z - the coordinates of the point where a collision can happen. If there is more than one such point, it should return a double[] containing exactly three zeroes. If collision of the two particles is impossible it should return an empty double[].

 

Definition

    
Class:ParticleCollision
Method:collision
Parameters:int, int, int, int, int, int
Returns:double[]
Method signature:double[] collision(int vx, int vy, int vz, int x0, int y0, int z0)
(be sure your method is public)
    
 

Notes

-PI can be considered equal to 3.14159265358979323846.
-All return values with either an absolute or relative error of less than 1.0E-9 are considered correct.
 

Constraints

-vx, vy and vz will each be between -10 and 10, inclusive.
-x0, y0 and z0 will each be between -10 and 10, inclusive.
 

Examples

0)
    
0
0
0
0
0
0
Returns: { }
The second trajectory is a single point (0, 0, 0), which doesn't lie on the first trajectory.
1)
    
2
4
1
-1
-1
0
Returns: {0.0, 1.0, 0.5 }
There is a single intersection point with coordinates (0, 1, 0.5).
2)
    
4
4
2
5
4
0
Returns: {0.0, 0.0, 0.0 }
There are two intersection points.
3)
    
0
0
1
1
0
0
Returns: {0.0, 0.0, 0.0 }
There are infinitely many intersection points.

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=8315

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=12173&pm=8315

Writer:

griffon

Testers:

PabloGilberto , Olexiy , gawry

Problem categories:

Geometry, Math, String Parsing