## Problem E. Enclosed by curves ≡

• problems
• en ru
 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.111s 0.021s 17