F. Пересечение отрезков: где именно

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

Те же два отрезка, что в классной задаче F, но теперь мало ответить «да или нет» - нужно описать само пересечение. Оно бывает пустым, точкой или отрезком.

Формат ввода

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

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

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

Для каждого запроса выведите 0, если общих точек нет.

Если пересечение - одна точка, выведите 1 и её координаты. Если отрезок - выведите 2 и координаты его концов в порядке возрастания $x$ , а при равных $x$ - возрастания $y$ . Координаты выводите с точностью $10^{-6}$ .

Примеры

ввод

3
0 0 2 0 1 -1 1 1
0 0 2 0 1 0 3 0
0 0 1 0 2 0 3 0

вывод

ввод

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

вывод

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

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