LaLa and Monster Hunting (Part 1)

A dreadful monster has been spotted in a forest near the city of $\color{red}{\text{m}} \color{brown}{\text{a}} \color{orange}{\text{g}} \color{blue}{\text{i}} \color{magenta} {\text{c}}$ Sharia. A group of valorous adventurers will hunt it down within a few days, before it hurts anyone. However, $\color{blue}{\text{LaLa}}$ knows the real reason those adventurers are willing to take the risk. The monster is known to produce a rare $\color{red}{\text{m}} \color{brown}{\text{a}} \color{orange}{\text{g}} \color{blue}{\text{i}} \color{magenta} {\text{c}}$ stone in its intestines, and the stone is quite beautiful. $\color{blue}{\text{LaLa}}$ wants to obtain the $\color{red}{\text{m}} \color{brown}{\text{a}} \color{orange}{\text{g}} \color{blue}{\text{i}} \color{magenta} {\text{c}}$ stone before the adventurers do.

$\color{blue}{\text{LaLa}}$ will first locate the monster with her $\color{red}{\text{m}} \color{brown}{\text{a}} \color{orange}{\text{g}} \color{blue}{\text{i}} \color{magenta} {\text{c}}$. $\color{blue}{\text{LaLa}}$ has placed several $\color{red}{\text{m}} \color{brown}{\text{a}} \color{orange}{\text{g}} \color{blue}{\text{i}} \color{magenta} {\text{c}}$ tools in the forest, and each tool has a power.

Draw a circle centered at each $\color{red}{\text{m}} \color{brown}{\text{a}} \color{orange}{\text{g}} \color{blue}{\text{i}} \color{magenta} {\text{c}}$ tool, with radius equal to its power. $\color{blue}{\text{LaLa}}$'s $\color{red}{\text{m}} \color{brown}{\text{a}} \color{orange}{\text{g}} \color{blue}{\text{i}} \color{magenta} {\text{c}}$ locates the monster if and only if the convex hull of the circles contains the monster's location. Write a program that determines whether $\color{blue}{\text{LaLa}}$ will be able to locate the monster.

The input is given in the following format:

$N$

$x\_0$ $y\_0$ $r\_0$

$x\_1$ $y\_1$ $r\_1$

$\vdots$

$x\_{N-1}$ $y\_{N-1}$ $r\_{N-1}$

$N$ is the number of $\color{red}{\text{m}} \color{brown}{\text{a}} \color{orange}{\text{g}} \color{blue}{\text{i}} \color{magenta} {\text{c}}$ tools in the forest. The $i$-th tool is located at $(x\_i, y\_i)$ and has power $r\_i$. The monster is at $(0, 0)$.

The input satisfies the following constraints:

• All the numbers in the input are integers.
• $1 \le N \le 1\\,000\\,000$
• $-1\\,000\\,000 \le x\_i, y\_i \le 1\\,000\\,000$ for all integers $0 \le i < N$
• $0 \le r\_i \le 1\\,000\\,000$ for all integers $0 \le i < N$
• The distance between point $(0, 0)$ and the boundary of the convex hull of $N$ circles, $i$-th of which is centered at $(x\_i, y\_i)$ and has radius $r\_i$, is at least $1$.

If $\color{blue}{\text{LaLa}}$'s $\color{red}{\text{m}} \color{brown}{\text{a}} \color{orange}{\text{g}} \color{blue}{\text{i}} \color{magenta} {\text{c}}$ will successfully locate the monster, print 'Yes'. Otherwise, print 'No'. You may print each character in either case (lower or upper).

The figures below show the tool placements for the sample tests. The red curve is the boundary of the convex hull.

Test 1	Test 2	Test 3