Tennis is a popular game. Consider a simplified view of a tennis game from directly above. The game will appear to be played on a 2 dimensional rectangle, where each player has his own court, a half of the rectangle. Consider the players and the ball to be points moving on this 2D plane. The ball can be assumed to always move with fixed velocity (speed and direction) when it is hit by a player. The ball changes its velocity when hit by the other player. And so on, the game continues.
Chef also enjoys playing tennis, but in n+1$n + 1$ dimensions instead of just 3. From the perspective of the previously discussed overhead view, Chef's court is an n$n$-dimensional hyperrectangle which is axis-aligned with one corner at (0,0,0,…,0)$(0, 0, 0, \dots, 0)$ and the opposite corner at (l1,l2,l3,…,ln$(l_1, l_2, l_3, \dots, l_n$). The court of his opponent is the reflection of Chef's court across the n−1$n - 1$ dimensional surface with equation x1=0$x_1 = 0$.
At time t=0$t=0$, Chef notices that the ball is at position (0,b2,…,bn)$(0, b_2, \dots, b_n)$ after being hit by his opponent. The velocity components of the ball in each of the n$n$ dimensions are also immediately known to Chef, the component in the ith$i^{th}$ dimension being vi$v_i$. The ball will continue to move with fixed velocity until it leaves Chef's court. The ball is said to leave Chef's court when it reaches a position strictly outside the bounds of Chef's court. Chef is currently at position (c1,c2,…,cn)$(c_1, c_2, \dots, c_n)$. To hit the ball back, Chef must intercept the ball before it leaves his court, which means at a certain time the ball's position and Chef's position must coincide.
To achieve this, Chef is free to change his speed and direction at any time starting from time t=0$t=0$. However, Chef is lazy so he does not want to put in more effort than necessary. Chef wants to minimize the maximum speed that he needs to acquire at any point in time until he hits the ball. Find this minimum value of speed smin$s_{min}$.
Note: If an object moves with fixed velocity →v$\vec{v}$ and is at position →x$\vec{x}$ at time 0$0$, its position at time t$t$ is given by →x+→v⋅t$\vec{x} + \vec{v} \cdot t$.

-----Input-----
- The first line contains t$t$, the number of test cases. t$t$ cases follow.
- The first line of each test case contains n$n$, the number of dimensions.
- The next line contains n$n$ integers l1,l2,…,ln$l_1, l_2, \dots, l_n$, the bounds of Chef's court.
- The next line contains n$n$ integers b1,b2,…,bn$b_1, b_2, \dots, b_n$, the position of the ball at t=0$t=0$.
- The next line contains n$n$ integers v1,v2,…,vn$v_1, v_2, \dots, v_n$, the velocity components of the ball.
- The next line contains n$n$ integers, c1,c2,…,cn$c_1, c_2, \dots, c_n$, Chef's position at t=0$t=0$.

-----Output-----
- For each test case, output a single line containing the value of smin$s_{min}$. Your answer will be considered correct if the absolute error does not exceed 10−2$10^{-2}$.

-----Constraints-----
- 1≤t≤1500$1 \leq t \leq 1500$
- 2≤n≤50$2 \leq n \leq 50$
- 1≤li≤50$1 \leq l_i \leq 50$
- 0≤bi≤li$0 \leq b_i \leq l_i$ and b1=0$b_1 = 0$
- −10≤vi≤10$-10 \leq v_i \leq 10$ and v1>0$v_1 > 0$
- 0≤ci≤li$0 \leq c_i \leq l_i$
- It is guaranteed that the ball stays in the court for a non-zero amount of time.

-----Sample Input-----
2
2
3 4
0 2
2 -2
2 2
3
10 10 10
0 0 0
1 1 1
5 5 5

-----Sample Output-----
2.0000
0.0000

-----Explanation-----
Case 1:  The court is 2-dimentional.

The ball's trajectory is marked in red. For Chef it is optimal to move along the blue line at a constant speed of 2 until he meets the ball at the boundary.
Case 2: The court is 3-dimensional and the ball is coming straight at Chef. So it is best for Chef to not move at all, thus smin=0$s_{min} = 0$.

Difficulty: VERY_HARD
Tags: Geometry

Sorting

Mathematics

Complete search
Skill types: Sorting

Complete search

Starter code:

Solutions:
EPS = 1e-08
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():
		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
	ans = method1()
	print('%.12f' % (ans,))


eps = 1e-08
t = int(input())
for ii in range(t):
	n = int(input())
	l = [int(i) for i in input().split()]
	b = [int(i) for i in input().split()]
	v = [int(i) for i in input().split()]
	c = [int(i) for i in input().split()]
	greatest_time = l[0] / v[0]
	for i in range(1, n):
		if v[i] > 0:
			greatest_time = min(greatest_time, (l[i] - b[i]) / v[i])
		elif v[i] < 0:
			greatest_time = min(greatest_time, -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 ternsearch():
		if b == c:
			return 0
		(lo, hi) = (0, greatest_time)
		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
	ans = ternsearch()
	print('%.12f' % (ans,))


import math
for i in range(int(input())):
	n = int(input())
	bound = [int(i) for i in input().split()]
	ball = [int(i) for i in input().split()]
	speed = [int(i) for i in input().split()]
	chef = [int(i) for i in input().split()]
	cspeed = 0
	time = float('inf')
	for i in range(n):
		if speed[i] > 0:
			a = (bound[i] - ball[i]) / speed[i]
			time = min(a, time)
		elif speed[i] < 0:
			a = abs(ball[i] / speed[i])
			time = min(a, time)
	a = b = c = 0
	for i in range(n):
		c += speed[i] ** 2
		a += (ball[i] - chef[i]) ** 2
		b += 2 * speed[i] * (ball[i] - chef[i])
	if a == 0:
		print(0)
	else:
		x = -b / (2 * a)
		if x >= 1 / time:
			cspeed = c - b ** 2 / (4 * a)
			print(math.sqrt(cspeed))
		else:
			cspeed = a / time ** 2 + b / time + c
			print(math.sqrt(cspeed))


EPS = 1e-08
EPS_ANS = 0.001
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))
	try:
		func = lambda t: p / t / t + q / t + r
	except:
		pass

	def method1():
		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():
		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,))