Aircraft

SRM 347 · 2007-05-01 · by StevieT

SRM 347 · 2007-05-01 · by StevieT · Geometry, Simple Math, Simulation

Show categories

Class Name: Aircraft

Return Type: String

Method Name: nearMiss

Arg Types: (vector<int>, vector<int>, vector<int>, vector<int>, int)

Problem Statement

In aviation, a "near miss" occurs if the distance between two aircraft at some point in time is less than or equal to some threshold distance R. At a moment in time, the positions and velocities of two aircraft are known exactly. Assuming that each aircraft continues to fly with constant speed and direction, you need to work out if the aircraft will undergo a near miss now or at some point in the future.

You will be given the threshold distance R and the positions and velocities of the aircraft in 4 int[]s: p1, v1, p2 and v2. The position of the first aircraft in 3-D cartesian space is given by (p1[0] , p1[1] , p1[2]) and its velocity vector by (v1[0] , v1[1] , v1[2]) and similarly the second aircraft's position and velocity are given by (p2[0] , p2[1] , p2[2]) and (v2[0] , v2[1] , v2[2]). So, if an aircraft's initial position is the vector p and its velocity vector is v, the position of this aircraft at some future time t will be p + v * t. You should return a String containing "YES" if the aircraft will undergo a near miss now or in the future or "NO" if they won't (quotes for clarity).

Notes

The distance between two points (x1, y1, z1) and (x2, y2, z2) is given by sqrt((x1-x2)2 + (y1-y2)2 + (z1-z2)2).

Constraints

p1, v1, p2 and v2 will contain exactly 3 elements.
Each element of p1, v1, p2 and v2 will be between -10000 and 10000, inclusive.
R will be between 0 and 10000, inclusive.

Examples

{15,50,5}
{25,1,0}
{161,102,9}
{-10,-10,-1}
10
Returns: "YES"

At time 4, the first aircraft will be at position {115,54,5} and the second at {121,62,5}, which is the first point in time at which they are exactly 10 distance units apart.

{0,0,0}
{2,2,0}
{9,0,5}
{-2,2,0}
5
Returns: "YES"

At time 2.25, aircraft 1 will be at {4.5, 4.5, 0} and aircraft 2 at {4.5, 4.5, 5}, exactly a distance of 5 units apart.

{0,0,0}
{-2,2,0}
{9,0,5}
{2,2,0}
5
Returns: "NO"

The aircraft are flying away from each other here, so the distance always increases with time.

{-4921,250,5852}
{-2,1,-2}
{-2,-1729,-9307}
{-2,0,0}
9864
Returns: "YES"

{-6987,-881,-5232}
{0,-2,-2}
{9835,-872,8837}
{-1,-2,-4}
8755
Returns: "YES"

{-2838,-7940,-2936}
{1,1,-2}
{532,3850,9590}
{1,0,-3}
3410
Returns: "YES"

The closest approach of the aircraft occurs at time 12,158

14)

{-8509,9560,345}
{-89,-33,62}
{-5185,-1417,2846}
{-58,24,26}
8344
Returns: "YES"

A near miss occurs between times 111 and 112

19)

{-7163,-371,-2459}
{-59,-41,-14}
{-2398,-426,-5487}
{-43,27,67}
5410
Returns: "NO"

The aircraft almost have a near miss between times 15 and 16, but stay just outside the threshold distance.

35)

{1774,-4491,7810}
{-12,19,-24}
{2322,3793,9897}
{-12,19,-24}
10000
Returns: "YES"

The aircraft are here flying with identical velocities, so the distance between them never changes. The distance at time 0 is lower than the threshold, so a near miss is already underway.

Submissions are judged against all 166 archived test cases, of which 9 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class Aircraft with a public method string nearMiss(vector<int> p1, vector<int> v1, vector<int> p2, vector<int> v2, int R) · 166 test cases · 2 s / 256 MB per case