G. Пересечение прямых

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

Каждая прямая задана двумя различными точками, через которые проходит. Определите, пересекаются ли прямые, и если пересекаются в одной точке - найдите её.

Формат ввода

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

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

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

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

Если прямые пересекаются ровно в одной точке, выведите 1 и координаты точки с точностью $10^{-6}$ .

Примеры

ввод

3
0 0 1 1 1 0 -1 2
1 17 5 20 4 40 2 18
2 2 3 3 5 5 10 10

вывод

1 0.5 0.5
1 1.9756097560975610 17.7317073170731707
2

ввод

2
0 0 1 0 0 1 1 1
0 0 1 0 0 0 2 0

вывод

0
2

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

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