Задача №114682. Точки на плоскости

Даны n точек на плоскости и q запросов следующего вида:

  • 1 x 1 y 1 x 2 y 2 ( x 1 ≠ x 2 или y 1 ≠ y 2 ). Рассмотрим прямую, проходящую через точки ( x 1 , y 1 ) и ( x 2 , y 2 ) . Существуют две полуплоскости, для которых данная прямая является границей. Рассмотрим ту из них, в которую попадает точка ( x 1 + y 2 - y 1 , y 1 + x 1 - x 2 ) . Другими словами, если рассмотреть направленный вектор из ( x 1 , y 1 ) в ( x 2 , y 2 ) , то требуемая полуплоскость будет лежать справа. Вам необходимо проверить, принадлежит ли хотя бы одна из данных точек заданной полуплоскости. Обратите внимание, что прямая принадлежит полуплоскости, поэтому точки, попадающие на прямую, учитываются.

  • 2 x 1 y 1 x 2 y 2 ( x 1 ≠ x 2 или y 1 ≠ y 2 ). Рассмотрим квадрат, противоположными вершинами которого являются точки ( x 1 , y 1 ) и ( x 2 , y 2 ) . Обратите внимание, что стороны этого квадрата не обязательно параллельны осям координат. Необходимо проверить, есть ли хотя бы одна заданная точка, которая лежит внутри или на границе квадрата.

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

В первой строке заданы два целых числа n и q ( 1 ≤ n , q ≤ 100 000 ) — количество точек и количество запросов.

В следующих n строках содержатся пары целых чисел x i , y i ( 1 ≤ x i , y i ≤ 10 8 ), описывающие координаты точек на плоскости.

В следующих q строках заданы запросы в формате, описанном выше. ( 1 ≤ x i , 1 , y i , 1 , x i , 2 , y i , 2 ≤ 10 8 )

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

Для каждого запроса выведите « Yes », если в заданном объекте лежит хотя бы одна точка и « No » — иначе.

Система оценки

Тесты к этой задаче состоят из восьми групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов необходимых групп.

Дополнительные ограничения
Группа Баллы n q Необх. группы Комментарий
0 0 – – – Тесты из условия.
1 11 n ≤ 1000 q ≤ 1000 – Для всех i верно, что t i = 1 .
2 12 – – 1 Для всех i верно, что t i = 1 .
3 5 n ≤ 1000 q ≤ 1000 – Для всех i верно, что t i = 2 и x i , 1 - x i , 2 = y i , 1 - y i , 2 .
4 16 – – 3 Для всех i верно, что t i = 2 и x i , 1 - x i , 2 = y i , 1 - y i , 2 .
5 12 n ≤ 1000 q ≤ 1000 0, 1, 3
6 17 n ≤ 30 000 q ≤ 30 000 0, 1, 3, 5
7 9 n ≤ 60 000 q ≤ 60 000 0, 1, 3, 5, 6
8 18 – – 0 - 7

Примеры
Входные данные
4 4
4 7
5 8
6 4
9 6
1 9 11 8 4
1 3 7 8 2
1 3 6 8 1
1 13 6 3 11
Выходные данные
Yes
Yes
No
No
Входные данные
4 8
4 7
5 8
6 4
9 6
1 9 11 8 4
1 3 7 8 2
1 3 6 8 1
1 13 6 3 11
2 6 4 5 8
2 6 6 7 7
2 7 5 9 11
2 5 3 6 6
Выходные данные
Yes
Yes
No
No
Yes
No
Yes
Yes
Сдать: для сдачи задач необходимо войти в систему