원을 넘지 않고 지나가기

시간 제한1초메모리 제한256 MB

요약

최대 100개 원의 원주를 하나도 넘지 않고 두 점을 잇는 곡선이 있는지 판정합니다.

난이도: 보통10점 중 6점
유형: 그래프, 기하, BFS
정답자: 아직 제출이 없습니다

문제

평면에 원이 하나 이상 놓여 있다. 서로 다른 두 원은 중심이 다르거나 반지름이 다르다. 원끼리 겹칠 수는 있지만, 세 개 이상의 원이 함께 공유하는 영역이나 점은 없다. 한 원이 다른 원을 완전히 품거나 두 원이 서로 다른 두 점에서 만날 수는 있어도, 두 원의 둘레가 한 점에서 닿는 일은 없다.

두 점 $P$ 와 $Q$ 가 주어질 때, 어느 원의 둘레도 지나지 않고 두 점을 잇는 경로가 있는지 판정하는 프로그램을 작성하시오. 경로는 원의 둘레를 지나지만 않으면 어떤 곡선이어도 된다. 원 배치 하나마다 점 쌍이 하나 이상 주어진다.

입력

입력은 여러 데이터 세트로 이루어진다. 각 데이터 세트의 형식은 다음과 같다.

$n$ $m$

$Cx_1$ $Cy_1$ $r_1$

...

$Cx_n$ $Cy_n$ $r_n$

$Px_1$ $Py_1$ $Qx_1$ $Qy_1$

...

$Px_m$ $Py_m$ $Qx_m$ $Qy_m$

첫 줄에는 공백으로 구분된 정수 $n$ 과 $m$ 이 주어진다. $n$ 은 원의 개수이며 $1 \le n \le 100$ 이다. $m$ 은 점 쌍의 개수이며 $1 \le m \le 10$ 이다. 이어지는 $n$ 개 줄에는 각각 공백으로 구분된 정수 세 개가 주어진다. $(Cx_i, Cy_i)$ 는 $i$ 번째 원의 중심이고 $r_i$ 는 그 반지름이다. 그 다음 $m$ 개 줄에는 각각 공백으로 구분된 정수 네 개가 주어지며, 두 점 $P_j = (Px_j, Py_j)$ 와 $Q_j = (Qx_j, Qy_j)$ 의 좌표를 나타낸다. 이 두 점이 $j$ 번째 점 쌍이다. 좌표와 반지름은 $0 \le Cx_i \le 10000$ , $0 \le Cy_i \le 10000$ , $1 \le r_i \le 1000$ , $0 \le Px_j \le 10000$ , $0 \le Py_j \le 10000$ , $0 \le Qx_j \le 10000$ , $0 \le Qy_j \le 10000$ 를 만족한다. $P_j$ 와 $Q_j$ 는 서로 다른 점이고, 어느 원의 둘레 위에도 놓이지 않는다.

입력의 끝은 공백으로 구분된 0 두 개로 이루어진 줄로 나타낸다.

출력

데이터 세트마다 결과 $m$ 개를 공백으로 구분해 한 줄에 출력한다. $j$ 번째 결과는 $P_j$ 와 $Q_j$ 를 잇는 경로가 있으면 YES, 없으면 NO이다.

예제1

예제 1

입력

5 3
0 0 1000
1399 1331 931
0 1331 500
1398 0 400
2000 360 340
450 950 1600 380
450 950 1399 1331
450 950 450 2000
1 2
50 50 50
0 10 100 90
0 10 50 50
2 2
50 50 50
100 50 50
40 50 110 50
40 50 0 0
4 1
25 100 26
75 100 26
50 40 40
50 160 40
50 81 50 119
6 1
100 50 40
0 50 40
50 0 48
50 50 3
55 55 4
55 105 48
50 55 55 50
20 6
270 180 50
360 170 50
0 0 50
10 0 10
0 90 50
0 180 50
90 180 50
180 180 50
205 90 50
180 0 50
65 0 20
75 30 16
90 78 36
105 30 16
115 0 20
128 48 15
128 100 15
280 0 30
330 0 30
305 65 42
0 20 10 20
0 20 10 0
50 30 133 0
50 30 133 30
90 40 305 20
90 40 240 30
16 2
0 0 50
0 90 50
0 180 50
90 180 50
180 180 50
205 90 50
180 0 50
65 0 20
115 0 20
90 0 15
280 0 30
330 0 30
305 65 42
75 40 16
90 88 36
105 40 16
128 35 250 30
90 50 305 20
0 0

예상 출력

YES NO NO
YES NO
NO NO
NO
YES
YES NO NO YES NO NO
NO NO