A. Шестнадцать расстояний

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

Даны четыре точки $A$ , $B$ , $C$ , $D$ . По первой паре построены три объекта — отрезок $AB$ , луч $AB$ (из $A$ через $B$ ) и прямая $AB$ ; по второй паре — отрезок $CD$ , луч $CD$ и прямая $CD$ .

Найдите все шестнадцать расстояний: от каждого из объектов $\{A, [AB], \text{луч } AB, \text{прямая } AB\}$ до каждого из $\{C, [CD], \text{луч } CD, \text{прямая } CD\}$ .

Формат ввода

В первой строке $q$ ( $1 \le q \le 2 \cdot 10^4$ ) — количество запросов. В каждой из следующих $q$ строк восемь целых чисел $x_A$ , $y_A$ , $x_B$ , $y_B$ , $x_C$ , $y_C$ , $x_D$ , $y_D$ , по модулю не превосходящих $10^4$ .

Гарантируется, что $A \ne B$ и $C \ne D$ .

Формат вывода

Для каждого запроса выведите шестнадцать чисел в одной строке: расстояния от $A$ , от отрезка $AB$ , от луча $AB$ и от прямой $AB$ — до $C$ , до отрезка $CD$ , до луча $CD$ и до прямой $CD$ соответственно.

Ответ принимается с абсолютной или относительной погрешностью $10^{-6}$ .

Примеры

ввод

1
1 2 7 1 5 6 8 2

вывод

5.656854249 5.600000000 5.600000000 5.600000000 4.603171645 1.414213562 1.400000000 1.400000000 4.603171645 1.150792911 0.000000000 0.000000000 4.603171645 1.150792911 0.000000000 0.000000000

ввод

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

вывод

1.000000000 1.000000000 1.000000000 1.000000000 1.000000000 1.000000000 1.000000000 1.000000000 1.000000000 1.000000000 1.000000000 1.000000000 1.000000000 1.000000000 1.000000000 1.000000000
1.000000000 1.000000000 1.000000000 0.000000000 0.000000000 0.000000000 0.000000000 0.000000000 0.000000000 0.000000000 0.000000000 0.000000000 0.000000000 0.000000000 0.000000000 0.000000000
3.162277660 3.162277660 3.162277660 3.000000000 3.000000000 3.000000000 3.000000000 3.000000000 3.000000000 3.000000000 3.000000000 3.000000000 3.000000000 3.000000000 3.000000000 3.000000000

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

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