F. Пересечение отрезков

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

Даны два отрезка (возможно, вырожденные в точку). Есть ли у них хотя бы одна общая точка?

Задача выглядит простой, и в ней больше всего вырожденных случаев из всего занятия.

Формат ввода

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

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

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

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

Примеры

ввод

3
1 2 1 2 1 2 1 2
3 3 5 6 5 6 3 3
1 1 7 4 5 3 3 2

вывод

YES
YES
YES

ввод

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

вывод

NO
YES
YES

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

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