codeforces#P1949I. Disks
Disks
Description
You are given $n$ disks in the plane. The center of each disk has integer coordinates, and the radius of each disk is a positive integer. No two disks overlap in a region of positive area, but it is possible for disks to be tangent to each other.
Your task is to determine whether it is possible to change the radii of the disks in such a way that:
- Disks that were tangent to each other remain tangent to each other.
- No two disks overlap in a region of positive area.
- The sum of all radii strictly decreases.
The first line contains an integer $n$ ($1\le n \le 1000$) — the number of disks.
The next $n$ lines contain three integers each. The $i$-th of such lines contains $x_i$, $y_i$ ($-10^9 \leq x_i, y_i \leq 10^9$), and $r_i$ ($1 \leq r_i \leq 10^9$) — the coordinates of the center, and the radius, of the $i$-th disk.
Print $\texttt{YES}$ if it is possible to change the radii in the desired manner. Otherwise, print $\texttt{NO}$.
Input
The first line contains an integer $n$ ($1\le n \le 1000$) — the number of disks.
The next $n$ lines contain three integers each. The $i$-th of such lines contains $x_i$, $y_i$ ($-10^9 \leq x_i, y_i \leq 10^9$), and $r_i$ ($1 \leq r_i \leq 10^9$) — the coordinates of the center, and the radius, of the $i$-th disk.
Output
Print $\texttt{YES}$ if it is possible to change the radii in the desired manner. Otherwise, print $\texttt{NO}$.
5
0 2 1
0 0 1
4 -3 4
11 0 3
11 5 2
4
2 2 2
7 2 3
7 7 2
2 7 3
YES
NO
Note
In the first sample, one can decrease the radii of the first and third disk by $0.5$, and increase the radius of the second disk by $0.5$. This way, the sum of all radii decreases by $0.5$. The situation before and after changing the radii is depicted below.
In the second sample, depicted below, there is no way to change the radii of the disks in the desired manner.