Skip to content

Instantly share code, notes, and snippets.

@meooow25
Last active February 19, 2019 23:10
Show Gist options
  • Save meooow25/242832232f4233b055d5cc1feb20002f to your computer and use it in GitHub Desktop.
Save meooow25/242832232f4233b055d5cc1feb20002f to your computer and use it in GitHub Desktop.
# CLTNIS
# Author: meooow
EPS = 1e-8
EPS_ANS = 1e-3
for t in range(int(input())):
n = int(input())
l = list(map(int, input().split()))
b = list(map(int, input().split()))
v = list(map(int, input().split()))
c = list(map(int, input().split()))
t_exit = l[0] / v[0]
for i in range(1, n):
if v[i] > 0:
t_exit = min(t_exit, (l[i] - b[i]) / v[i])
elif v[i] < 0:
t_exit = min(t_exit, -b[i] / v[i])
p = sum((b[i] - c[i]) ** 2 for i in range(n))
q = sum(2 * (b[i] - c[i]) * v[i] for i in range(n))
r = sum(vi ** 2 for vi in v)
func = lambda t: p / t / t + q / t + r
def method1():
# Get minima directly
if b == c:
return 0
t_opt = t_exit
if q < 0:
t_opt = min(-2 * p / q, t_exit)
return max(0, func(t_opt)) ** 0.5
def method2():
# Ternary search
if b == c:
return 0
lo, hi = 0, t_exit
while hi - lo > EPS:
d = (hi - lo) / 3
m1 = lo + d
m2 = m1 + d
if func(m1) <= func(m2):
hi = m2
else:
lo = m1
return max(0, func(lo)) ** 0.5
assert abs(method1() - method2()) < EPS_ANS
ans = method1()
print('%.12f' % (ans,))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment