Problem E. Enclosed by curves

Author:A. Baranov   Time limit:1 sec
Input file:Standard input   Memory limit:512 Mb
Output file:Standard output  

Statement

Novice programmer Vasya develops his own vector graphics editor. In addition to the usual primitives (like rectangles, circles, straight lines) his editor also supports working with objects of complex shapes, which are described using spline curves.

Each such curve consists of several pieces, in sequence one after the other, each of which is given by a parametric equation of the following form:

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

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

where t — scalar parameter, changing in range of [0, 1].

Vasya uses closed spline curves to describe complex shapes. One of his tasks is to determine for every given point whether it lies inside such a figure.

Input format

The beginning of the input contains an integer N, followed by 8 × N real numbers, specifying the coefficients of the corresponding splines

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

Next there is integer M, followed by 2 × M real numbers, specifying the coordinates of the points (Xj, Yj).

Output format

Output must contain M integers (answers to each query):
1 — if the point is inside the contour,
0 — if it is outside.

Constraints

Within the specified accuracy, the contour is continuous and does not have self-intersections.

The distance from each point to the boundary of the contour is not less than 10 − 5.

The contour lies entirely within the rectangular area [ − 10, 10] × [ − 10, 10].

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

Sample tests

No. Standard input Standard output
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

Explanation

Для эффективного решения нашей задачи построим вспомогательную структуру, воспользовавшись методом полос.

Для начала дополним набор узлов имеющихся у нас сплайнов точками их перегиба по направлению X.

Чтобы найти точку перегиба кубической функции, достаточно приравнять к нулю ее производные.

Иначе говоря, для этого нам потребуется найти корни квадратного уравнения:
3 ⋅ AXi ⋅ t2 + 2 ⋅ BXi ⋅ t + CXi = 0.

Выберем из них те, которые попадают в соответствующие интервалы [0, 1].
Тем самым определим набор параметрических интервалов, на которых функции Xi(t) сохраняют монотонный вид.

Выполним подразбиение имеющихся сплайнов по соответствующим интервалам.

Посчитаем значения X(t) на границах указанных интервалов, и отсортируем их вдоль оси абсцисс.

Полученные значения припишем сплайнам, к узлам которых они относятся.

При этом расположим их в порядке возрастания, пометив их как левая и правая.

Проведя через них вертикальные линии, получим разбиение плоскости набором полос.

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

Начнем последовательный обход от самой левой вертикальной линии.
В процессе обхода будем добавлять в список сплайны,
у которых левые границы лежат на очередной прямой,
и исключать те, у которых — правые.

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

Для этого достаточно определить Y координаты точек
пересечения каждого такого сплайна с прямой,
проходящей через середину текущей полосы.

Выбрав для примера самый нижний сплайн из самой левой полосы, мы можем определить ориентацию контура,
просто посмотрев направление роста параметра от левой до правой его точки.

Если параметр возрастает, значит направление левостороннее,
если убывает, значит правостороннее.

В результате получим поисковую структуру, на основе которой можно будет выполнять запросы.

Для очередной входной точки двоичным поиском определим полосу, в которую она попадает.

Если она не попадает ни в одну из полос, то лежит очевидно снаружи контура.

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

Для этого достаточно сравнить Y координату точки и точку пересечения
сплайна с проходящей через нее прямой.

Далее нам достаточно сравнить направление соответствующего
сплайна с ориентацией контура.


0.079s 0.013s 15