문제2416--미사일 방어

2416: 미사일 방어

실행시간 제한: 1 Sec  메모리사용 제한: 128 MB
제출: 179  통과: 50
[제출] [채점기록] [묻고답하기]

문제 설명

네모마을에는 발전소가 하나 있습니다. 이 발전소는 직사각형 모양이며 위 그림과 같이 위치해 있습니다. 왼쪽 아래 꼭지점의 좌표는 $(-1000, -1000)$이며, 오른쪽 위 꼭지점의 좌표는$(1000, 1000)$ 입니다.

동그라미마을은 네모마을을 공격하기 위해 $N$개의 미사일을 발사하였습니다. 각 미사일은 떨어질 지점 $(X_{i}, Y_{i})$을 중심으로 반지름 $R_{i}$인 원 모양의 영역에 피해를 줍니다.

네모마을에서는 발전소에 피해를 줄 수 있는 모든 미사일을 요격하려고 합니다. 다만 미사일의 범위가 발전소에 한 점에만 피해를 주는 경우는 카운트하지 않습니다.

여러분은 네모마을을 돕기 위해 어떤 미사일이 발전소에 피해를 줄 수 있는지를 계산하는 프로그램을 작성하여야 합니다.

입력 설명

첫 줄에 미사일의 수 $N$이 주어집니다. $N$은 $1,000$ 이하의 자연수입니다. 그 다음 $N$줄에 걸쳐 $i$번째 미사일의 위치 $X_{i}, Y_{i}$ 와 피해를 주는 범위 $R_{i}$ 가 각각 공백 하나를 사이에 두고 주어집니다. $(-10,000 \leq X_{i}, Y_{i} \leq 10,000, 1 \leq R_{i} \leq 20,000 )$

모든 입력은 정수로 주어집니다.

출력 설명

첫 줄에 요격해야 할 미사일의 수 $K$를 출력합니다. 그 다음 $K$줄에 미사일의 번호를 한줄에 하나씩 출력합니다.

출력되는 숫자는 오름차순으로 정렬되어 출력되야 합니다.

입력 예시 Copy

4
-934 987 20
-1005 -1004 3
1005 0 5
8231 9823 18276

출력 예시 Copy

2
1
4

도움

첫 번째 미사일과 네 번째 미사일은 발전소에 피해를 줄 수 있으며, 두 번째 미사일은 피해를 줄 수 없습니다. 세 번째 미사일의 범위는 건물의 한 점에만 피해를 주는 경우로, 카운트하지 않습니다.

출처/분류