Задача E. Enclosed by curves

Автор:A. Baranov   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:512 Мб
Выходной файл:Стандартный выход  

Условие

Начинающий программист Вася разрабатывает собственный векторный графический редактор. Помимо обычных примитивов (наподобие прямоугольников, окружностей, прямых) его редактор также поддерживает работу с объектами сложной формы, для описания которых используются сплайновые кривые.

Каждая такая кривая состоит из нескольких кусков, последовательно идущих друг за другом, каждый из которых задается параметрическим уравнением следующего вида:

Xi(t) = AXi ⋅ t3 + BXi ⋅ t2 + CXi ⋅ t + DXi;

Yi(t) = AYi ⋅ t3 + BYi ⋅ t2 + CYi ⋅ t + DYi,

где t — скалярный параметр, изменяющийся в диапазоне [0, 1].

Для описания сложных фигур Вася использует замкнутые сплайновые кривые. Одна из стоящих перед ним задач — определить для каждой из заданных точек попадание внутрь такой фигуры.

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

В начале входных данных содержится целое N, за которым следует 8 × N вещественных чисел, задающих коэффициенты соответствующих сплайнов

AXi, BXi, CXi, DXi,
AYi, BYi, CYi, DYi.

Далее записано целое число M, за которым следует 2 × M вещественных чисел, задающих координаты точек (Xj, Yj).

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

Выходные данные должны содержать последовательность из M целых чисел (ответов на каждый запрос):
1 — если соответствующая точка лежит внутри контура,
0 — если лежит снаружи.

Ограничения

В пределах заданной точности контур непрерывен и не имеет самопересечений.

Расстояние от каждой из точек до границы контура не меньше 10 − 5.

Контур целиком лежит внутри прямоугольной области [ − 10, 10] × [ − 10, 10].

1 ≤ N ≤ 1000, 1 ≤ M ≤ 105.

Примеры тестов

Стандартный вход Стандартный выход
1
6
 3.53200 -4.87400  1.66600 -0.46000
 0.67600 -0.70800  0.26600 -0.20200
 1.74000 -2.86600  0.84800 -0.13600
 1.29000 -1.88200  0.61200  0.03200
-1.40400  2.10600 -0.51200 -0.41400
-0.17200  0.25800  0.10600  0.05200
-1.40000  1.57000  0.00000 -0.22400
-0.22200  0.01600 -0.00000  0.24400
-3.42400  4.60600 -1.06000 -0.05400
 0.11600  0.22800 -0.63400  0.03800
 0.60200 -0.07000 -1.06000  0.06800
 1.77400 -2.52800  0.80400 -0.25200

8
-0.23000 -0.27000
-0.37094 -0.10086
 0.00000  0.15040
-0.39010  0.20360
-0.31067  0.04029
-0.20000 -0.08960
 0.03000 -0.05071
-0.18603  0.17014
0
1
1
0
1
1
0
1

0.099s 0.020s 17