L. Расстояние между отрезками

1000 мс · 256 МБ · всё или ничего

Даны два отрезка. Найдите расстояние между ними - минимум расстояния по всем парам точек.

В первой строке - число запросов $q$ ( $1 \le q \le 10^5$ ).

В следующих $q$ строках - по восемь целых чисел: концы двух отрезков. Координаты по модулю не превосходят $10^4$ ; отрезки могут быть вырожденными.

Для каждого запроса выведите расстояние между отрезками с точностью $10^{-6}$ .

ввод

3
0 0 1 0 0 1 1 1
0 0 2 2 2 0 0 2
0 0 1 0 3 0 4 0

вывод

1
0
2

ввод

2
0 0 0 0 3 4 3 4
0 0 4 0 2 5 2 1

вывод

5
1

Разбор идеи от автора задачи. Сначала попробуйте сами.

Войдите, чтобы отправлять решения.