Challenge: Spheres
Scor cont: 30.0 / 30
Submission status: Accepted
Submission score: 1.0
Submission ID: 464727551
Limbaj: python3
Link challenge: https://www.hackerrank.com/challenges/spheres/problem
Cerinta
Initially, two non-touching spheres of radii _R1_ and _R2_ are lying in space at rest. Both of them are then given accelerations _a1_ and _a2_ respectively at time=0. Find whether they will ever come in contact. Their initial positions are represented as _(x1,y1,z1)_ and _(x2,y2,z2)_ respectively. Accelerations have respective components in 3D. They are represented as _(a1<sub>i</sub>,a1<sub>j</sub>,a1<sub>k</sub>)_ and _(a2<sub>i</sub>,a2<sub>j</sub>,a2<sub>k</sub>)_ respectively.
**Input Format**
The first line contains _T_, the number of test cases.
Each test case consists of five lines, where the first line contains _R1_ and _R2_. The next two lines contain position and acceleration of the first sphere. The next two lines after this contain position and acceleration of the second sphere. All numbers in input are integers.
**Output Format**
For each test case, print `YES`, if the spheres come in contact. Otherwise, print `NO` (quotes for clarity).
**Constraints**
1 ≤ _T_ ≤ 10<sup>4</sup>
1 ≤ _R1_, _R2_ ≤ 10<sup>2</sup>
-10<sup>2</sup> ≤ _x1_, _y1_, _z1_ , _x2_ , _y2_ , _z2_ ≤ 10<sup>2</sup>
-10<sup>2</sup> ≤ _a1<sub>i</sub>_ , _a1<sub>j</sub>_ , _a1<sub>k</sub>_ , _a2<sub>i</sub>_ , _a2<sub>j</sub>_ , _a2<sub>k</sub>_ ≤ 10<sup>2</sup>
**Sample input**
2
1 2
0 0 0
-1 0 0
4 0 0
1 0 0
1 2
0 0 0
100 0 0
4 0 0
0 0 0
**Sample output**
NO
YES
**Explanation**
For first testcase, both spheres go in opposite directions, so they'll never come in contact.
For second testcase, second sphere is not moving while first sphere is accelerating towards the second sphere. So they come in contact.Cod sursa
#!/bin/python3
import os
import sys
import math
from decimal import *
#inner product of two vectors (x,y,z)(a,b,c)
def inner(list1, list2):
res = 0
for i in range(3):
res += list1[i] * list2[i]
return res
#helping func--> gives |P|^2. P is explained later.
def P(dete, Dacc, Dpos):
return inner(Dacc,Dacc)/4*(dete*dete) + inner(Dacc,Dpos)*dete + inner(Dpos,Dpos)
def solve(r1, r2, p1, a1, p2, a2):
#the distance that their centers have to keep (always)
k = r1 + r2
#difference of their acceleration
Dacc = list()
#difference of their position( initialy )
Dpos = list()
Dacc.append(a1[0]-a2[0])
Dacc.append(a1[1]-a2[1])
Dacc.append(a1[2]-a2[2])
Dpos.append(p1[0]-p2[0])
Dpos.append(p1[1]-p2[1])
Dpos.append(p1[2]-p2[2])
#if they already collide
if inner(Dpos, Dpos) <=k:
return "YES"
#to solve it we have to evaluate the position they have at time t
#for their centers is respectively:
#pos1(t) = acc1*t^2 (+initial speed*t but they rest at start, so = 0) + pos1_init
#pos2(t) = acc2*t^2 (+initial speed*t but they rest at start, so = 0) + pos2_init
#then their diference which we call P (that is computed by our func)
#must always be <k
#so P = Dacc*t^2 + Dpos. But P is vector. we want its magnitude to check: |P|<k
#so from vector analysis its |P| = sqrt(P*P) where P*P = (P,P) aka their inner product:
#P*P = inner(Dacc,Dacc)/4*t^4 + inner(Dacc,Dpos)*t^2 + inner(Dpos,Dpos) ___(1)___
#so we check for solutions of |P|=k (because at start we checked if |P|>=k, so we want
#to see if it reaches or touches) ==> |P|^2 -k^2 = 0 ==>
#P*P-k^2=0 ==> (from ___(1)___) we solve this new quadratic equation where x = t^2 and
#a,b,c:
a = inner(Dacc, Dacc)/4
b = inner(Dacc, Dpos)
c = inner(Dpos, Dpos) - k*k
#if determinant is negative its unsolvable because our x is t^2 so we cant have this
if (b*b - 4*a*c) < 0:
return "NO"
#then we take ta solution with the '+' sign on the determinant again for t^2
#<<< and here was a technical problem. if you use a mere math.sqrt() you lose >>>
#<<< precision which will change your final check ( I mean |P| < k ). To find >>>
#<<< this given testcase2 and its results took my evening. I just subtracted >>>
#<<< from c a small value like 0.00000001 and it worked for some testcases so >>>
#<<< I figured out it was a precision problem. So i googled it and found the >>>
#<<< solution with Decimal. It gives you good precision. >>>
sol1 = (-1*Decimal(b) + Decimal(b*b - 4*a*c).sqrt())
#if my solution is negative its unsolvable becaue again x = t^2 (t^2 >= 0)
if sol1 <0:
return "NO"
#then to use it for evaluating |P|^2 again typecast sol1 from Decimal to float.
value1 = P(float(sol1), Dacc, Dpos)
#if value1 = P*P < k*k then it means that my solution got parabolas peak and
#didnt go over k. so for any other t I know that |P|<k. I did this check with
#squares becaue again sqrt() gives you problems.
if value1<k*k:
return "NO"
else:
return "YES"
if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')
t = int(input())
for t_itr in range(t):
r1R2 = input().split()
r1 = int(r1R2[0])
r2 = int(r1R2[1])
position1 = list(map(int, input().rstrip().split()))
acceleration1 = list(map(int, input().rstrip().split()))
position2 = list(map(int, input().rstrip().split()))
acceleration2 = list(map(int, input().rstrip().split()))
result = solve(r1, r2, position1, acceleration1, position2, acceleration2)
fptr.write(result + '\n')
fptr.close()
HackerRank Geometry – Spheres