K. Disk Covering
time limit per test
1 s
memory limit per test
2048 MB
input
standard input
output
standard output

On a vast, flat green meadow, there are several golden disks in the shape of perfect circles from ancient times. According to legend, if one chants a spell, the area covered by the disks will turn into flames, fending off enemy attacks. When the enemy comes, you can hide in a place completely surrounded by disks, yet not on the disks, thus isolated from the outside world by the flames.

Given the positions and sizes of the disks, determine whether such a hiding place exists.

Input

The first line contains an integer $$$N$$$, representing the number of disks. In the following $$$N$$$ lines, the $$$i^{\texttt{th}}$$$ line contains three integers that describe disk $$$i$$$: the x-coordinate $$$x_i$$$, the y-coordinate $$$y_i$$$ of its center, and its radius $$$r_i$$$.

Output

A single integer, $$$1$$$ if such a place exists, or $$$0$$$ otherwise.

Limits

  •  $$$1 \leqslant N \leqslant 250$$$;
  •  $$$-10^9 \leqslant x_i, y_i\leqslant 10^9$$$ for all $$$i \leqslant N$$$;
  •  $$$1 \leqslant r_i \leqslant 10^9$$$ for all $$$i \leqslant N$$$;
  •  There are no three disks whose circular outlines intersect at a common point;
  •  Among all intersection points of the circular outlines of any two disks, the distance between any two intersection points is greater than or equal to 1;
  •  There are no two disks whose circular outlines are tangent to each other (i.e. have exactly one intersection point);
  •  For two disks whose circular outlines do not intersect, the distance between any point on the circular outline of one disk and any point on the circular outline of the other disk is always greater than or equal to 1.
Examples
Input
4
-6 0 8
-4 10 7
4 4 6
8 14 2
Output
0
Input
5
4 -2 5
-4 -2 5
-8 8 8
4 6 5
-6 4 2
Output
1
Input
3
420 580 230
200 200 200
600 200 210
Output
0
Note

Sample Explanation 1

In this sample, there isn't any place that is completely surrounded by disks, yet not on the disks.

Sample Explanation 2

In this sample, $$$(-0.5, 3)$$$ is one of the places we can hide. It is surrounded by disks, yet not on the disks. Note that although all the inputs are integers, the hiding place does not necessarily have to be an integer point.

Sample Explanation 3

In this sample, there isn't any place that is completely surrounded by disks, yet not on the disks.