Informatica Online Judge

  로미오와 줄리엣 [1194 / 04AA]

Time Limit(Test case) : 2000(ms)
Number of users who solved : 13   Total Tried : 25


The Champion of this Problem (C++) : N/A
My Best Submission (C++) : N/A

[CCC 2006 Day1]

Background

먼 옛날, 로미오 집안과 줄리엣 집안은 부모들에 의해 서로 만나지 않도록 분리되었다. 하지만, 로미오와 줄리엣의 사랑은 변하지 않았고, 깡통-실 전화를 이용해 연락하며 서로의 사랑을 유지했다.

시간이 흘러 어떤 것들은 변하고, 어떤 것들은 변하지 않았다. 로미오의 6대 손인 줄리아(화성 행성)는 로미안(엡실론 186-베타 행성)과 사랑에 빠졌지만, 부모들의 상대방 집안에 대한 증오 때문에 로미안과 이야기 할 수 없었다.

줄리아와 로미안이 서로 만나지 못하도록, 그 둘의 부모들은 장거리 통신이 안 되는 우주선들에 둘을 갈라놓았다.

그래서 줄리아와 로미안은 레이저를 이용한 모르스(morse) 부호를 사용해 서로에게 메시지를 보내야만 한다.

로미안과 줄리아의 시점에서 메시지들은, 송신기와 수신기 사이가 차단되어있지 않으면, 레이저를 이용해 무한의 거리만큼 전송될 수 있다. 아주 먼 미래이기 때문에 레이저는 우주를 가로질러 거의 즉시 전달된다.

따라서 레이저가 전달될 때에 행성들과 우주선들은 고정된 상태라고 생각할 수 있다.

로미안과 줄리아가 있는 우주선들의 좌표를 3차원 직교좌표라고 생각할 때, 로미안과 줄리아가 서로 통신할 수 있을지 판단하고자 하는데, 통신에 사용되는 레이저는 행성들에 의해 자주 가로막힌다.

Input

로미안과 줄리아 우주선의 3차원 정수 좌표가 3개씩 공백을 두고, 두 줄로 입력된다.

그 다음에 그 우주 공간에 놓여있는 행성들의 개수 n(1<= n <=2000)이 입력된다.

그 다음 n개의 줄에는 n개 행성들의 3차원 정수 좌표(a, b, c)(0 <= |a|, |b|, |c| <= 5000)와 행성의 반지름 r(0<= r <= 5000)이 순서대로 공백을 두고 입력된다.

행성의 좌표가 (a, b, c), 반지름이 r이라고 하면 (x-a)^2 + (y-b)^2 + (z-c)^2 = r^2 의 식을 만족한다.

참고
- 로미안과 줄리안은 서로 충돌할 수 있기 때문에 10^-8 거리이내(+같은 좌표)에 있지 않으며, 행성 내부에 있을 수도 없다.
- 행성과 10^-8 미만의 차이를 두고 레이저가 지나가면, 행성에 가려지게 된다.

Output

로미안과 줄리안의 통신을 방해하는 행성의 개수 b(0<= b <=n)를 출력한다.

IO Example

입력
100 100 100
-100 -100 -100
2
0 0 0 2
50 60 -50 5

출력
1

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]