eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Пересечение отрезков - 2

Пересечение отрезков - 2

Лимит времени 8.5 секунд
Лимит использования памяти 128 MiB

На декартовой плоскости задано n отрезков координатами своих концов. Определить, пересекаются ли они. Множество отрезков пересекается, если среди них существует хотя бы два, которые имеют как минимум одну общую точку.

Входные данные

Каждая строка содержит целочисленные координаты концов отрезка (x_1, y_1) - (x_2, y_2). Известно, что n 6*10^5 и -2000x_1, y_1, x_2, y_22000.

Выходные данные

Вывести "intersect" если отрезки пересекаются и "NOT intersect" иначе.

Пример

Входные данные #1
1 1 6 3
6 1 9 3
2 5 7 3
2 3 4 3
7 2 10 1
Выходные данные #1
intersect