Problem C. Comparison of topologies

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

Statement

Consider a set of rings on the plane. Each of these rings can be described by coordinates of its center (x, y), internal and external radius: q, r. It is known that any two circles bounding different rings do not cross each other.

Let us define a continuous mapping on this set that includes the next operations:

It is assumed that during these operations the bounding circles shouldn't intersect. Also, any ring shouldn't become singular (circle or point) during resizing. In other words, this mapping must keep the basic topological properties of the initial set.

Your program must, given two sets of the rings M1 and M2, determine whether there exist a continuous mapping to obtain M2 from M1 or not. It is assumed that order of rings in these sets may be different.

Input file format

Input file contains integer n — number of rings in the each set, followed by 4 × n floating point numbers xi, yi, qi, ri — parameters of the rings of M1, and then followed by another 4 × n numbers — similar parameters of the rings of M2,

Output file format

Output file must contain a single integer 1 — if M2 can be obtained by continuous mapping from M1 or 0 — otherwise.

Constraints

All input values have no more than 3 digits after the decimal point.

 − 105 < xi, yi < 105, 0 < qi < ri < 105, 1 ≤ n ≤ 2000

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
 3
 0.000  0.000  1.000  2.000
 0.000  0.000  0.500  1.500
 5.000 -7.000  1.000  2.000
 0.000  0.000  1.000  6.000
-5.000  9.000  0.500  2.000
 0.000  0.000  0.500  1.500
1
2
 3
 0.000 -2.500  4.790  6.800
 0.000 -2.180  3.260  4.000
 9.810  2.630  1.000  1.500
 0.000 -8.500  2.000  6.800
-0.940 -4.000  0.500  1.500
-3.970 -8.970  1.000  1.500
0

0.110s 0.009s 15