R & J

면접 대비

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

요약

3차원 공간에서 두 우주선과 n개의 구가 주어질 때, 두 우주선을 잇는 선분이 지나는 구의 개수를 센다.

난이도: 보통10점 중 6점
유형: 기하, 수학, 구현, 완전 탐색
정답자: 아직 제출이 없습니다

문제

먼 옛날, 로미(Romy)와 줄스(Jules)는 부모의 반대로 헤어져 다시는 만나지 못하게 되었지만, 깡통 전화기를 통해 사랑을 이어 갔다. 세월이 흘러 로미의 6대손 줄리아(Julia, 화성 출신)는 로미안(Romian, 엡실론 186-베타 행성 출신)과 사랑에 빠졌지만, 역시 부모의 반목 때문에 서로 이야기할 수 없었다. 부모들은 두 사람이 만나지 못하도록 각각 장거리 통신 장비가 없는 우주선에 태워 버렸다. 그래서 줄리아와 로미안은 레이저로 모스 부호 메시지를 주고받아야만 한다.

이 시대에는 레이저가 우주 공간을 무한한 거리까지 즉시 전달되며, 보내는 쪽과 받는 쪽을 잇는 직선 경로가 무언가에 가로막히지만 않으면 메시지가 전달된다. 행성과 우주선은 모두 정지해 있다고 가정한다.

두 우주선의 3차원 격자 좌표가 주어질 때, 두 사람이 레이저로 통신할 수 있는지 판단하려고 한다. 문제는 레이저가 중간에 있는 행성들에 자주 가로막힌다는 것이다. 레이저를 가로막는 행성의 수, 즉 두 우주선을 잇는 선분이 통과하는 행성의 수를 세어라.

입력

첫 두 줄에 로미안과 줄리아의 우주선 격자 좌표가 각각 주어진다. 각 좌표는 공백으로 구분된 세 정수로 이루어진다.

그다음 줄에는 현재 우주 구역에 있는 행성의 개수를 나타내는 정수 $n$ ( $1 \le n \le 2000$ )이 주어진다. 이어지는 $n$ 개의 줄에 각 행성이 공백으로 구분된 네 정수로 주어진다. 앞의 세 정수는 행성 중심의 좌표이고, 네 번째 정수는 행성의 반지름이다. 중심이 $(a, b, c)$ 이고 반지름이 $r$ 인 행성은 방정식 $(x-a)^2 + (y-b)^2 + (z-c)^2 = r^2$ 로 나타낼 수 있다. $0 \le r \le 5000$ 이며, 모든 좌표 $(a, b, c)$ 에 대해 $0 \le |a|, |b|, |c| \le 5000$ 이다.

또한 다음을 가정할 수 있다.

로미안과 줄리아는 어떤 행성과도 $10^{-8}$ 단위 이내로 가까이 있지 않으며(충돌하게 되므로), 행성 내부에 있지도 않다(불가능하므로).
로미안과 줄리아는 같은 위치에 있지 않다.
레이저가 어떤 행성에 부딪힌다면, 반지름이 $10^{-8}$ 단위 더 작은 행성에도 부딪힌다. 레이저가 어떤 행성을 비껴간다면, 반지름이 $10^{-8}$ 단위 더 큰 행성도 비껴간다.

출력

레이저를 가로막는 행성의 수를 나타내는 정수 $b$ ( $0 \le b \le n$ ) 하나를 출력한다. 가로막는 행성이 없으면 0을 출력한다.

예제4

예제 1

입력

100 100 100
-100 -100 -100
2
0 0 0 2
50 60 -50 5

예상 출력

예제 2
입력
```
0 0 0
10 0 0
1
0 100 0 5
```
예상 출력
```
0
```
예제 3
입력
```
0 0 0
20 0 0
1
10 0 0 1
```
예상 출력
```
1
```

예제 4

입력

예상 출력