Read problem statement in Mandarin chinese and Vietnamese. 

Suzumo is the coach of the ChefLand OI team. Physical condition is very important in any olympiad, so he wants to make the children run a bit as a warmup.

The team consists of $N$ children numbered $1$ through $N$ standing at some positions on the $x$-axis. For each valid $i$, the initial $x$-coordinate of the $i$-th kid is $x_{i}$, the running velocity of the $i$-th kid is constant and equal to $v_{i}$.

Suzumo wants to assign a running direction (left or right, i.e. in the direction of decreasing or increasing $x$-coordinate) to each kid; the children start running at time $0$ in the assigned directions. Afterwards, Suzumo will measure the smallest time $t$ at which some kid passes another one. Help Suzumo compute the maximum time $t$ if he can assign the directions arbitrarily!

Note: Child $i$ *passes* child $j$ at time $t_{ij}$ if their coordinates satisfy $x_{i} < x_{j}$ at any time $t < t_{ij}$ and $x_{i} > x_{j}$ at any time $t > t_{ij}$, or if they satisfy $x_{i} > x_{j}$ at any time $t < t_{ij}$ and $x_{i} < x_{j}$ at any time $t > t_{ij}$.

------  Input ------

The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains a single integer $N$.
$N$ lines follow. For each valid $i$, the $i$-th of these lines contains two space-separated integers $x_{i}$ and $v_{i}$.

------  Output ------

For each test case, print a single line containing one real number — the maximum possible time $t$, or $-1$ if it is possible to assign directions in such a way that no kid ever passes another. Your answer will be considered correct if it has an absolute or relative error less than or equal to $10^{-6}$.

------  Constraints  ------
$1 ≤ T ≤ 100$
$1 ≤ N ≤ 50$
$1 ≤ x_{i}, v_{i} ≤ 10^{9}$ for each valid $i$
no two children have the same initial positions

----- Sample Input 1 ------ 
1
3
10 10
20 30
30 10
----- Sample Output 1 ------ 
0.5
----- explanation 1 ------ 
Example case 1: One optimal assignment of directions is left, right, right.

Source: codechef | Difficulty: VERY_HARD
Tags: Greedy algorithms

Sorting

Complete search


Solutions:
LEFT = 0
RIGHT = 1
T = int(input())
coordinates = None

def f():
	ans = [[100000000000.0, 100000000000.0]]
	for i in range(1, len(coordinates)):
		ans.append([0, 0])
		distance = coordinates[i][0] - coordinates[i - 1][0]
		velocity = coordinates[i][1] + coordinates[i - 1][1]
		time_taken = distance / velocity
		ans[i][LEFT] = max(ans[i][LEFT], min(ans[i - 1][RIGHT], time_taken))
		velocity = coordinates[i - 1][1] - coordinates[i][1]
		if velocity > 0:
			time_taken = distance / velocity
			ans[i][RIGHT] = max(ans[i][RIGHT], min(ans[i - 1][RIGHT], time_taken))
		else:
			ans[i][RIGHT] = max(ans[i][RIGHT], ans[i - 1][RIGHT])
		velocity = coordinates[i][1] - coordinates[i - 1][1]
		if velocity > 0:
			time_taken = distance / velocity
			ans[i][LEFT] = max(ans[i][LEFT], min(ans[i - 1][LEFT], time_taken))
		else:
			ans[i][LEFT] = max(ans[i][LEFT], ans[i - 1][LEFT])
		ans[i][RIGHT] = max(ans[i][RIGHT], ans[i - 1][LEFT])
	return ans[-1][RIGHT]
for t in range(T):
	N = int(input())
	coordinates = [tuple(map(int, input().split())) for _ in range(N)]
	coordinates.sort()
	answer = f()
	if answer == 100000000000.0:
		answer = -1
	print(answer)


for query in range(int(input())):
	n = int(input())
	child = []
	for i in range(n):
		child.append([int(v) for v in input().split()])
	child.sort()
	d = [float('inf'), float('inf')]
	for i in range(1, n):
		if child[i][1] <= child[i - 1][1]:
			left_left = d[0]
		else:
			left_left = min(d[0], (child[i][0] - child[i - 1][0]) / float(child[i][1] - child[i - 1][1]))
		left_right = d[0]
		right_left = min((child[i][0] - child[i - 1][0]) / float(child[i][1] + child[i - 1][1]), d[1])
		if child[i][1] >= child[i - 1][1]:
			right_right = d[1]
		else:
			right_right = min(d[1], (child[i][0] - child[i - 1][0]) / float(child[i - 1][1] - child[i][1]))
		d = [max(left_left, right_left), max(left_right, right_right)]
	if max(d) == float('inf'):
		print(-1)
	else:
		print(max(d))


import math
tc = int(input())
while tc > 0:
	n = int(input())
	children = []
	for i in range(n):
		temp = list(map(int, input().split()))
		children.append(temp)
	children.sort()
	data = [math.inf, math.inf]
	for i in range(1, n):
		if children[i - 1][1] >= children[i][1]:
			ll = data[0]
		else:
			ll = min(data[0], (children[i][0] - children[i - 1][0]) / float(children[i][1] - children[i - 1][1]))
		rl = min(data[1], (children[i][0] - children[i - 1][0]) / float(children[i][1] + children[i - 1][1]))
		lr = data[0]
		if children[i - 1][1] <= children[i][1]:
			rr = data[1]
		else:
			rr = min(data[1], (children[i][0] - children[i - 1][0]) / float(children[i - 1][1] - children[i][1]))
		data = [max(ll, rl), max(lr, rr)]
	if max(data) is math.inf:
		print(-1)
	else:
		print(max(data))
	tc -= 1


def check(mid, arr):
	pr = 0
	n = len(arr)
	an = [0]
	for i in range(1, n):
		x1 = arr[i - 1][0]
		x2 = arr[i][0]
		v1 = arr[i - 1][1]
		v2 = arr[i][1]
		if pr == 0:
			if x2 - x1 >= mid * (v2 - v1):
				pr = 0
			else:
				pr = 1
		elif x2 - x1 >= mid * (v2 + v1):
			pr = 0
		elif x2 - x1 >= mid * (v1 - v2):
			pr = 1
		else:
			return False
		an.append(pr)
	return True
for nitish in range(int(input())):
	n = int(input())
	arr = []
	for i in range(n):
		ar = list(map(int, input().strip().split(' ')))
		arr.append(ar)
	arr.sort()
	low = 0.0
	high = 10 ** 20 * 1.0
	if check(high, arr):
		print(-1)
		continue
	ans = 0.0
	while abs(low - high) > 1e-06:
		mid = (low + high) / 2
		if check(mid, arr):
			low = mid
			ans = max(ans, mid)
		else:
			high = mid
	print(ans)


def optimal_assignment(cs):
	PREC = 1e-10
	cs.sort()
	(lo, hi) = (0.0, 2000000000.0)
	if has_solution(hi, cs):
		return -1
	for _ in range(1000):
		mid = lo + (hi - lo) / 2
		if has_solution(mid, cs):
			lo = mid
		else:
			hi = mid
		if hi - lo < PREC:
			break
	return lo + (hi - lo) / 2

def has_solution(t, cs):
	prev_p = -1e+50
	for (p, v) in cs:
		new_p = p - v * t
		if new_p > prev_p:
			prev_p = new_p
		else:
			new_p = p + v * t
			if new_p > prev_p:
				prev_p = new_p
			else:
				return False
	return True
t = int(input())
for _ in range(t):
	n = int(input())
	cs = []
	for _ in range(n):
		cs.append(tuple(map(int, input().strip().split())))
	print(optimal_assignment(cs))


from math import ceil, log
t = int(input())
for test in range(t):
	n = int(input())
	arr = [[-1, -1]]
	for i in range(n):
		arr.append(list(map(int, input().split())))
	if n == 1:
		print(-1)
		continue
	arr.sort()
	ans = [None, (int(2000000000.0), int(2000000000.0))]
	for i in range(2, n + 1):
		tmp = int(2000000000.0)
		if arr[i - 1][1] < arr[i][1]:
			tmp = (arr[i][0] - arr[i - 1][0]) / (arr[i][1] - arr[i - 1][1])
		tmp2 = (arr[i][0] - arr[i - 1][0]) / (arr[i][1] + arr[i - 1][1])
		tmp = min(ans[i - 1][0], tmp)
		tmp2 = min(ans[i - 1][1], tmp2)
		x = max(tmp, tmp2)
		tmp = int(2000000000.0)
		if arr[i - 1][1] > arr[i][1]:
			tmp = (arr[i][0] - arr[i - 1][0]) / (arr[i - 1][1] - arr[i][1])
		tmp = min(ans[i - 1][1], tmp)
		tmp2 = min(ans[i - 1][0], int(2000000000.0))
		y = max(tmp2, tmp)
		ans.append((x, y))
	if max(ans[-1]) == int(2000000000.0):
		print(-1)
	else:
		print(max(ans[-1]))