원을 넘지 않고 지나가기

아직 제출이 없습니다시간 제한1초메모리 제한256 MB

문제

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

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

입력

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

nn mm

Cx1Cx_1 Cy1Cy_1 r1r_1

...

CxnCx_n CynCy_n rnr_n

Px1Px_1 Py1Py_1 Qx1Qx_1 Qy1Qy_1

...

PxmPx_m PymPy_m QxmQx_m QymQy_m

첫 줄에는 공백으로 구분된 정수 nnmm이 주어진다. nn은 원의 개수이며 1n1001 \le n \le 100이다. mm은 점 쌍의 개수이며 1m101 \le m \le 10이다. 이어지는 nn개 줄에는 각각 공백으로 구분된 정수 세 개가 주어진다. (Cxi,Cyi)(Cx_i, Cy_i)ii번째 원의 중심이고 rir_i는 그 반지름이다. 그 다음 mm개 줄에는 각각 공백으로 구분된 정수 네 개가 주어지며, 두 점 Pj=(Pxj,Pyj)P_j = (Px_j, Py_j)Qj=(Qxj,Qyj)Q_j = (Qx_j, Qy_j)의 좌표를 나타낸다. 이 두 점이 jj번째 점 쌍이다. 좌표와 반지름은 0Cxi100000 \le Cx_i \le 10000, 0Cyi100000 \le Cy_i \le 10000, 1ri10001 \le r_i \le 1000, 0Pxj100000 \le Px_j \le 10000, 0Pyj100000 \le Py_j \le 10000, 0Qxj100000 \le Qx_j \le 10000, 0Qyj100000 \le Qy_j \le 10000를 만족한다. PjP_jQjQ_j는 서로 다른 점이고, 어느 원의 둘레 위에도 놓이지 않는다.

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

출력

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