#2416 미사일 방어

39  1 s   128 MB  

Description

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

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

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

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

Input

첫 줄에 미사일의 수 $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 )$

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

Output

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

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

Sample Input

Sample Output

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

HINT

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

Source

SHAKE! 예선대회