In Wolf town there are 2 big markets S and T. The distance between these markets is D. Chef Ciel would like to run 2 restaurants in Wolf town, where the first restaurant will be supplied by the market S and the second one will be supplied by the market T. The markets run delivery service without charge within some distance, D_{S} and D_{T} respectively. Near these markets there are many rival restaurants. So Ciel decides to build one of her restaurants exactly at the distance D_{S} from the market S, and build the other restaurant exactly at the distance D_{T} from the market T.
Chef Ciel would like to build her restaurants as close as possible to each other for convenient communication. Your task is to calculate the minimum distance that could be achieved between her restaurants.
Note. Wolf town can be considered as an infinite 2D Cartesian plane. The markets and Ciel's restaurants should be considered as points on a plane. The distance between the two points A and B, whose coordinates are (A_{x}, A_{y}) and (B_{x}, B_{y}) respectively, is defined by Dist(A, B) = ((A_{x} − B_{x})^{2} + (A_{y} − B_{y})^{2})^{1/2}.

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

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows. The only line of each test case contains three space-separated integers D_{S}, D_{T} and D.

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

For each test case, output a single line containing the minimum possible distance between Ciel's restaurants that could be achieved. The output must have an absolute or relative error at most 0.000001 (10^{−6}). Please, note that your output should not have more than 1000 digits after the decimal point, otherwise you may (or may not) get wrong answer or runtime error (SIGXFSZ).
Note also that the answer could be 0, which means that two Ciel's restaurants should be located at the same building.

------ Constraints ------ 

$1 ≤ T ≤ 2013$
$1 ≤ D_{S}, D_{T}, D ≤ 2013$
Just to reiterate, your output can have any number of digits after the decimal point unless it is too long (more than 1000 digits after decimal point). However your output must have an absolute or relative error at most 10^{−6}.
----- Sample Input 1 ------ 
4
15 15 50
15 15 18
43 88 200
2013 2013 2013
----- Sample Output 1 ------ 
20.000
0.0
69.00000
0

------ Explanation 0 ------ 

Example case 1. The distance between markets S and T is 50. Assume for simplicity that S has coordinates (0, 0) and T has coordinates (50, 0). Then Ciel could build her first restaurant RS at the point (15, 0) and the second restaurant RT at the point (35, 0). This will ensure that the distance between S and RS is DS = 15 and the distance between T and RT is DT = 15. The distance between restaurants appear to be 20 in this scenario. One can prove that this is the minimum possible distance.
Example case 2. Here Ciel can locate both her restaurants at the same place. Indeed, if S = (0, 0) and T = (18, 0) then Ciel could locate both her restaurants at the point R = (9, 12). To check this note that Dist(R, S) = ((9 ? 0)^2 + (12 ? 0)^2)^1/2 = (81 + 144)^1/2 = 225^{1}/2 = 15. Similarly it can be verified that Dist(R, T) = 15.
Example case 3. It is similar to the example case 1. If S = (0, 0) and T = (200, 0) then the best way is to locate Ciel's restaurants at the points RS = (43, 0) and RT = (112, 0). You can easily check by yourself that Dist(S, RS) = 43, Dist(T, RT) = 88 and Dist(RS, RT) = 69.

Difficulty: MEDIUM_HARD
Tags: Geometry

Constructive algorithms

Mathematics

Ad-hoc

Starter code:

Solutions:
for i in range(int(input())):
	(a, b, c) = map(int, input().split())
	if c > max(a, b):
		print(max(0, c - (a + b)))
	else:
		print(max(0, max(a, b) - c - min(a, b)))


for _ in range(int(input())):
	(ds, dt, d) = map(int, input().split())
	print(max(0, d - ds - dt, ds - d - dt, dt - d - ds))


t = int(input())
for i in range(t):
	(d1, d2, d) = map(int, input().split())
	print(max(0, d - d1 - d2, d1 - d - d2, d2 - d - d1))


def integer_list():
	return list(map(int, input().split()))

def main():
	if ds + dt < d:
		print(d - ds - dt)
	elif ds > d + dt:
		print(ds - d - dt)
	elif dt > d + ds:
		print(dt - d - ds)
	else:
		print(0)
t = int(input())
for _ in range(t):
	(ds, dt, d) = integer_list()
	main()


def solve():
	(d1, d2, d) = list(map(int, input().split()))
	print(max(0, d - d1 - d2, d1 - d - d2, d2 - d - d1))
t = int(input())
while t != 0:
	solve()
	t -= 1


t = int(input())
for _ in range(t):
	(ds, dt, d) = map(int, input().split())
	if ds + dt <= d:
		print(d - (ds + dt))
	else:
		print(max(0, max(d - (ds + dt), max(ds - (d + dt), dt - (d + ds)))))


for _ in range(int(input())):
	(d_s, d_t, d) = map(int, input().split())
	t_1 = max(0, d - d_t - d_s, d_s - d_t - d, d_t - d - d_s)
	print(t_1)


def distance(ds, dt, d):
	(ans1, ans3, ans4) = (0, 0, 0)
	if ds + dt < d:
		ans1 = d - ds - dt
	elif ds >= d + dt:
		ans3 = ds - d - dt
	elif dt >= d + ds:
		ans4 = dt - d - ds
	ans = max(0, ans1, ans3, ans4)
	print(ans)
for _ in range(int(input())):
	(ds, dt, d) = map(float, input().split())
	distance(ds, dt, d)


for i in range(int(input())):
	s = [int(x) for x in input().split()]
	if s[1] > s[0] + s[2]:
		print(s[1] - s[0] - s[2])
	elif s[2] > s[1] + s[0]:
		print(s[2] - s[1] - s[0])
	elif s[0] > s[1] + s[2]:
		print(s[0] - s[1] - s[2])
	else:
		print('0')


for _ in range(int(input())):
	(ds, dt, d) = map(int, input().split())
	if d >= ds + dt:
		print(float(d - ds - dt))
	elif dt < ds + d and ds < d + dt and (d < ds + dt):
		print('0.0')
	elif ds >= dt + d:
		print(float(ds - d - dt))
	elif dt >= ds + d:
		print(float(dt - ds - d))


for _ in range(int(input())):
	(a, b, c) = map(int, input().split())
	if a + b <= c:
		print('{:.4f}'.format(round(c - (a + b), 5)))
	elif max(a, b) > c + min(a, b):
		print('{:.4f}'.format(round(max(a, b) - (c + min(a, b)), 5)))
	else:
		print(0.0)


for _ in range(int(input().strip())):
	(s, t, d) = map(int, input().split())
	if d > max(s, t):
		if s + t > d:
			print(0)
		else:
			print(d - s - t)
	elif max(s, t) > d + min(s, t):
		print(max(s, t) - d - min(s, t))
	else:
		print(0)


__author__ = 'Ronald Kaiser'
__email__ = 'raios dot catodicos at gmail dot com'
for _ in range(int(input())):
	v = list(map(int, input().strip().split()))
	v.sort()
	print(v[2] - v[1] - v[0] if v[2] - v[1] - v[0] > 0 else 0)


t = int(input())
for I in range(t):
	d = sorted(list(map(int, input().split())))
	if d[2] - d[1] - d[0] < 0:
		print('0')
	else:
		print(d[2] - d[1] - d[0])


def main():
	from sys import stdin, stdout
	inp = stdin.readline
	out = stdout.write
	res = []
	t = int(inp().strip())
	for i in range(t):
		(ds, dt, d) = map(int, inp().strip().split())
		if ds <= dt + d and dt <= ds + d and (d <= dt + ds):
			res.append('0\n')
		elif ds >= dt + d:
			res.append(str(ds - (dt + d)) + '\n')
		elif dt >= ds + d:
			res.append(str(dt - (ds + d)) + '\n')
		elif d >= dt + ds:
			res.append(str(d - (dt + ds)) + '\n')
	for i in range(t):
		out(res[i])
main()


def integer_list():
	return list(map(int, input().split()))

def main():
	print(max(dt - d - ds, ds - d - dt, d - ds - dt, 0))
t = int(input())
for _ in range(t):
	(ds, dt, d) = integer_list()
	main()


t = int(input())
while t:
	(ds, dt, d) = [int(i) for i in input().split()]
	if d >= ds + dt:
		ans = d - (ds + dt)
	elif ds >= dt + d:
		ans = ds - (dt + d)
	elif dt >= d + ds:
		ans = dt - (d + ds)
	elif ds + dt > d or dt + d > ds or d + ds > dt:
		ans = 0
	print('{0:f}'.format(ans))
	t -= 1


__author__ = 'Ronald Kaiser'
__email__ = 'raios dot catodicos at gmail dot com'
for _ in range(int(input())):
	v = list(map(int, input().strip().split()))
	m = max(v)
	v.remove(m)
	x = m - v[1] - v[0]
	print(x if x > 0 else 0)


t = int(input())
for _ in range(t):
	(s, t, d) = map(int, input().split())
	a = []
	b = []
	if d >= max(s, t):
		for i in range(s + 1):
			a.append(i)
		for i in range(d, d - t - 1, -1):
			b.append(i)
		a = set(a)
		b = set(b)
		c = a.intersection(b)
		if len(c) > 0:
			print(0)
		else:
			e = d - (s + t)
			print(e)
	elif d >= max(s, t) - min(s, t):
		print(0)
	else:
		print(max(s, t) - min(s, t) - d)


def pint():
	return int(input())

def pmap():
	return map(int, input().strip().split())

def plist():
	return list(map(int, input().strip().split()))

def pstr():
	return input().strip()

def check(a, b, c):
	if a + b >= c and b + c >= a and (c + a >= b):
		return True
	else:
		return False
t = int(input())
while t:
	t -= 1
	(a, b, c) = plist()
	if check(a, b, c):
		print(0)
	else:
		d = sorted([a, b, c])
		print(d[2] - d[1] - d[0])


for _ in range(int(input().strip())):
	(ds, dt, d) = map(int, input().strip().split())
	(ds, dt) = (ds, dt) if ds > dt else (dt, ds)
	if abs(ds - dt) <= d <= ds + dt:
		print(0)
	elif ds + dt < d:
		print(d - ds - dt)
	else:
		print(abs(ds - dt) - d)


for _ in range(int(input())):
	v = list(map(int, input().strip().split()))
	v.sort()
	k = v[2] - v[1] - v[0]
	print(k if k > 0 else 0)


t = int(input())
while t > 0:
	t -= 1
	D = sorted(list(map(int, input().split())))
	if D[2] - D[1] - D[0] < 0:
		print('0')
	else:
		print(D[2] - D[1] - D[0])


T = int(input())
for i in range(T):
	(A, B, C) = map(int, input().split(' '))
	if A + B >= C:
		if B + C >= A and A + C >= B:
			print(0.0)
		else:
			print('%0.10f' % (max(A, B) - (min(A, B) + C)))
	else:
		print('%0.10f' % (C - (A + B)))


for _ in range(int(input())):
	(S, T, D) = map(int, input().split())
	S1 = 0
	S2 = 2 * S
	T1 = S + D - T
	T2 = S + D + T
	if S1 in range(T1, T2 + 1) and S2 in range(T1, T2 + 1) or (T1 in range(S1, S2 + 1) and T2 in range(S1, S2 + 1)):
		dist = [abs(S1 - T1), abs(S1 - T2), abs(S2 - T1), abs(S2 - T2)]
		print(min(dist))
	elif S1 in range(T1, T2 + 1) or S2 in range(T1, T2 + 1) or T1 in range(S1, S2 + 1) or (T2 in range(S1, S2 + 1)):
		print(0)
	else:
		dist = [abs(S1 - T1), abs(S1 - T2), abs(S2 - T1), abs(S2 - T2)]
		print(min(dist))


T = int(input())
ans = []
for _ in range(T):
	(DS, DT, D) = [int(i) for i in input().split()]
	ans.append(max(0, D - DS - DT, DS - DT - D, DT - DS - D))
for i in ans:
	print(i)


def mindis(a, b, c):
	res = 0
	if a >= b + c:
		res = a - b - c
	elif b >= a + c:
		res = b - a - c
	else:
		res = c - a - b
	return max(0, res)
t = int(input())
while t:
	t -= 1
	(a, b, c) = map(int, input().split())
	print(mindis(a, b, c))


for i in range(int(input())):
	(s, t, d) = map(int, input().split())
	print(max(0, d - s - t, t - s - d, s - t - d))


for t in range(int(input())):
	(ds, dt, d) = map(int, input().split())
	if ds + dt == d or (ds + dt > d and d + ds > dt and (d + dt > ds)):
		print(0)
	elif ds + dt < d:
		print(d - ds - dt)
	else:
		print(max(ds, dt) - min(ds, dt) - d)


for i in range(int(input())):
	(ds, dt, d) = [int(ds) for ds in input().split()]
	if d > max(dt, ds):
		print(max(0, d - (ds + dt)))
	else:
		print(max(0, max(ds, dt) - d - min(ds, dt)))


for q in range(int(input())):
	(ds, dt, d) = map(int, input().split())
	print(float(max(0, d - ds - dt, ds - dt - d, dt - ds - d)))


def soln(ds: int, dt: int, d: int) -> int:
	if max(ds, dt) > min(ds, dt) + d:
		return max(ds, dt) - (min(ds, dt) + d)
	return max(0, d - (ds + dt))
for _ in range(int(input())):
	(ds, dt, d) = map(int, input().split())
	print('{:.6f}'.format(soln(ds, dt, d)))


for _ in range(int(input())):
	(X, Y, D) = map(int, input().split())
	if D >= max(X, Y):
		if X + Y <= D:
			print(D - X - Y)
		else:
			print(0)
	elif D >= max(X, Y) - min(X, Y):
		print(0)
	else:
		print(max(X, Y) - min(X, Y) - D)


def value(a, b, c):
	sum = 0
	if a > b + c:
		sum = a - b - c
	elif b > a + c:
		sum = b - a - c
	else:
		sum = c - a - b
	sum = max(0, sum)
	return sum
t = int(input())
for i in range(t):
	(a, b, c) = map(int, input().split())
	print(value(a, b, c))


for i in range(int(input())):
	(a, b, c) = map(int, input().split(' '))
	if c > a + b:
		print('{:.6f}'.format(c - a - b))
	elif b > a + c:
		print('{:.6f}'.format(b - a - c))
	elif a > b + c:
		print('{:.6f}'.format(a - b - c))
	else:
		print('{:.6f}'.format(0))


t = int(input())
for T in range(t):
	(ds, dt, d) = [int(x) for x in input().split()]
	ans = 0
	ans = max(ans, d - (ds + dt))
	ans = max(ans, ds - (d + dt))
	ans = max(ans, dt - (d + ds))
	print(ans)


t = int(input())
while t:
	(ds, dt, d) = map(int, input().split())
	if d >= ds + dt:
		ans = d - ds - dt
	elif d < ds + dt and d + ds > dt and (d + dt > ds):
		ans = 0
	elif ds >= dt + d:
		ans = ds - d - dt
	elif dt >= ds + d:
		ans = dt - d - ds
	print(ans)
	t -= 1


for _ in range(int(input())):
	(DS, DT, D) = map(int, input().split())
	print(max(0, D - DS - DT, DS - D - DT, DT - DS - D))


t = int(input())
for _ in range(t):
	(ds, dt, d) = map(int, input().split())
	if ds + dt <= d:
		print(round(d - ds - dt, 1000))
	elif abs(ds - dt) <= d:
		print(0.0)
	elif ds > dt:
		print(round(ds - dt - d, 1000))
	else:
		print(round(dt - ds - d, 1000))


import math
for _ in range(int(input())):
	(s, t, d) = sorted(list(map(int, input().split())))
	print(max(0, d - t - s))


import math
t = int(input())
for case in range(t):
	vars = input().split()
	ds = int(vars[0])
	dt = int(vars[1])
	d = int(vars[2])
	dsum = ds + dt
	dmax = max(ds, dt)
	dmin = min(ds, dt)
	if dsum < d:
		print(d - ds - dt)
		continue
	if dsum == d:
		print(0)
		continue
	if dmax >= d + dmin:
		print(dmax - dmin - d)
		continue
	print(0)
	continue


for _ in range(int(input())):
	(a, b, c) = map(int, input().split())
	if a + b < c:
		print('%.7f' % (c - (a + b)))
	elif a < c and b < c and (a + b >= c):
		print(0)
	elif a > b:
		temp = a - c
		if temp > b:
			print('%.7f' % (temp - b))
		else:
			print(0)
	else:
		temp = b - c
		if temp > a:
			print('%.7f' % (temp - a))
		else:
			print(0)


test = int(input())
for _ in range(test):
	(Ds, Dt, D) = map(int, input().split())
	print(max(0, D - Ds - Dt, Ds - Dt - D, Dt - Ds - D))


t = int(input())
for _ in range(t):
	(ds, dt, d) = map(int, input().strip().split())
	if ds + dt > d and dt + d > ds and (ds + d > dt):
		print('{:0.1f}'.format(0))
	else:
		arr = [ds, dt, d]
		arr = sorted(arr, reverse=True)
		print('{:0.2f}'.format(arr[0] - arr[1] - arr[2]))


for _ in range(int(input())):
	(a, b, c) = map(int, input().split())
	print(max(0, a - b - c, b - c - a, c - b - a))


T = int(input())
for i in range(T):
	(a, b, c) = sorted(list(map(int, input().split())))
	print(max(c - b - a, 0))


x = int(input())
for j in range(x):
	(s, t, d) = map(int, input().split())
	t1 = max(0, d - t - s, s - t - d, t - d - s)
	print(t1)


for _ in range(int(input())):
	(S, T, D) = map(int, input().split())
	if S + T <= D:
		print(float(D - (S + T)))
	elif S + D <= T:
		print(T - (S + D))
	elif D + T <= S:
		print(S - (T + D))
	else:
		print(float(0))


T = int(input())
for t in range(T):
	(ds, dt, d) = map(int, input().split())
	print(max(0, d - ds - dt, ds - dt - d, dt - ds - d))


t = int(input())
for _ in range(t):
	(x, y, z) = list(map(int, input().strip().split()))
	d1 = min(x, y)
	d2 = max(x, y)
	d = z
	if d1 + d2 <= z:
		print(z - d1 - d2)
	elif d2 - d1 <= z:
		print(0)
	else:
		print(d2 - d1 - z)


for i in range(int(input())):
	(d1, d2, d) = map(int, input().split())
	if d1 + d2 >= d and d + d1 >= d2 and (d + d2 >= d1):
		print(float(0))
	elif d1 >= d2 + d:
		print(float(d1 - (d + d2)))
	elif d >= d1 + d2:
		print(float(d - (d1 + d2)))
	elif d2 >= d + d1:
		print(float(d2 - (d1 + d)))


test = int(input())
for _ in range(test):
	(a, b, c) = map(int, input().split())
	if c > max(a, b):
		print(max(0, c - (a + b)))
	else:
		print(max(0, max(a, b) - c - min(a, b)))