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

0.109s 0.023s 15