Hi everyone! Sorry for my english... I just want to tell you about
another way to solve this problem. In this task we must simply find
minimum of function dist(t) (d - distance). For this We must find d
(dist(t))/dt (differentiation, derivative of dist(t)). Then we must to
solve equation d(dist(t))/dt = 0 (this is condition of minimum or
maximum, but there it can be only minimum). I.e. dist(t) = sqrt(X^2 +
Y^2 + Z^2)
X(t) = S(xi + vxi*t)/N (
(dist(t))' = (sqrt(X^2 + Y^2 + z^2))' = (1/2*sqrt(X^2 + Y^2 + Z^2)) *
(X(t)^2 + Y(t)^2 + Z(t)^2) = (1/2*sqrt(X^2 + Y^2 + Z^2)) * 2(X(t)*(X
(t))' + Y(t)*(Y(t))' + Z(t)*(Z(t))') =
(1/2*sqrt(X^2+Y^2+Z^2))*2(S(xi+vxi*t)*S(vxi) + S(yi+vyi*t)*S(vyi) + S
(zi+vzi*t)*S(vzi))/N
I.e. (dist(t))' = 0 if S(xi+vxi*t)*S(vxi) + S(yi+vyi*t)*S(vyi) + S(zi
+vzi*t)*S(vzi) = 0! It is enough to find tmin!
S(xi)*S(vxi)+S(vxi)*t*S(vxi)+S(yi)*S(vyi)+S(vyi)*t*S(vyi)+S(zi)*S(vzi)
+S(vzi)*t*S(vzi)=0
--> t*(Svxi^2 + Svyi^2 + Svzi^2) = - (S(xi)*S(vxi) + S(yi)*S(vyi) + S
(zi)*S(vzi))
--> t = - (S(xi)*S(vxi) + S(yi)*S(vyi) + S(zi)*S(vzi))/(Svxi^2 +
Svyi^2 + Svzi^2)
When we have solved this equation we find tmin!
But we must check that Svxi^2 + Svyi^2 + Svzi^2 is not equal to 0.
Else the center of mass have stationary position, and then the minimum
time is equal to zero.
This is my solution in python:
input = open('fly.txt', 'r')
output = open('flyans.txt', 'w')
def summa(mas):
ans = 0
for i in mas:
ans += i
return ans
T = input.readline()
for t in xrange(int(T)):
x =[]
y = []
z = []
vx = []
vy = []
vz = []
n = int(input.readline())
for i in xrange(n):
c = input.readline()
c = map(int,c.split())
x.append(c[0])
y.append(c[1])
z.append(c[2])
vx.append(c[3])
vy.append(c[4])
vz.append(c[5])
sx = summa(x)
sy = summa(y)
sz = summa(z)
svx = summa(vx)
svy = summa(vy)
svz = summa(vz)
if svx == 0 and svy == 0 and svz == 0:
tmin = 0
else:
tmin = -float(sx*svx + sy*svy + sz*svz)/(svx**2 + svy**2 +
svz**2)
if tmin < 0:
tmin = 0
dmin = (((sx + svx*tmin)**2 + (sy + svy*tmin)**2 + (sz + svz*tmin)
**2)/float(n**2))**0.5
output.write('Case #' + str(t+1) + ': ' + "%.8f" %dmin + ' ' + "%.
8f" %tmin + '\n')
input.close()
output.close()
I will be happy if it is interesting to anybody! Thank you very much
if you read my solution! Good luck!
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"google-codejam" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/google-code?hl=en
-~----------~----~----~----~------~----~------~--~---
