Disks

시간 제한2초메모리 제한2048 MB

요약

정수 좌표 중심을 가진 서로 겹치지 않는 원들이 주어질 때, 접촉 관계를 유지하면서 반지름 합을 줄일 수 있는지 판정한다.

난이도: 어려움10점 중 8점
유형: 그래프, 기하, 수학, DFS
정답자: 아직 제출이 없습니다

문제

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 new radii are allowed to be arbitrary positive real numbers. The centers of the disks cannot be changed.

입력

The first line contains an integer $n$ ( $1 ≤ n ≤ 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 ≤ x\_i , y\_i ≤ 10^9$ ), and $r\_i$ ( $1 ≤ r\_i ≤ 10^9$ ) — the coordinates of the center, and the radius, of the $i$ -th disk.

출력

Print YES if it is possible to change the radii in the desired manner. Otherwise, print NO.

예제2

예제 1
입력
```
5
0 2 1
0 0 1
4 -3 4
11 0 3
11 5 2
```
예상 출력
```
YES
```
예제 2
입력
```
4
2 2 2
7 2 3
7 7 2
2 7 3
```
예상 출력
```
NO
```