| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 379 | 194 | 156 | 50.323% |
2차원 평면상에 살고 있는 푸앙이는 신입생으로 대학에 입학하게 되었다. 대학에 입학한 푸앙이는 활발한 성격으로 $N$명의 친구들을 사귀었고, 친구들을 1ドル$번, 2ドル$번, $\cdots,ドル $N$번으로 부르려고 한다.
푸앙이는 그중 몇몇 친구들과 함께 사진을 찍게 되었다. 친구들에게 찍은 사진을 받고 싶지만 움직이기 귀찮은 푸앙이는 이 사진들을 가만히 앉아서 에어드롭으로 받으려고 한다.
에어드롭은 보내는 휴대폰과 받는 휴대폰 사이의 버전 차이가 $T$ 이하이면서 유클리드 거리로 최대 $K$만큼 떨어진 거리의 기기에만 사진을 전송할 수 있으며, 푸앙이와 사진을 가지고 있었던 친구의 휴대폰 버전 차이가 $T$보다 크더라도 다른 친구들을 이용한 간접적인 경로가 있다면 사진을 전달받을 수 있다.
푸앙이는 자신이 알고 있는 $N$명의 친구들을 이용해 최대한 많은 사진을 전송받으려고 한다. 푸앙이가 받을 수 있는 사진을 모두 찾아보자.
첫 번째 줄에 친구의 수 $N$과 에어드롭의 최대 거리 $K$와 최대 휴대폰 버전 차이 $T$가 공백으로 구분되어 주어진다.
두 번째 줄에는 푸앙이의 좌표와 푸앙이의 휴대폰 버전인 $X_p,ドル $Y_p,ドル $V_p$가 공백으로 구분되어 주어진다.
세 번째 줄부터 $N$개의 줄에 걸쳐 푸앙이 친구들의 정보가 주어진다. 그중 $i$번째 줄에는 $i$번 친구의 정보 $X_i,ドル $Y_i,ドル $V_i,ドル $P_i$가 공백으로 구분되어 주어진다. $X_i,ドル $Y_i$는 좌표, $V_i$는 휴대폰 버전을 의미한다. $P_i$가 0이라면 푸앙이와 사진을 찍지 않았음을, 1이라면 푸앙이와 사진을 찍었음을 의미한다.
첫 번째 줄에 푸앙이가 받을 수 있는 사진을 처음에 가지고 있었던 친구들의 번호를 공백으로 구분하여 오름차순으로 출력한다.
만약 푸앙이가 받을 수 있는 사진이 아무것도 없다면 0을 출력한다.
5 4 3 5 2 4 2 2 1 0 2 5 4 1 2 8 7 1 4 9 11 1 7 6 4 1
2 3
해당 그림에서 실선은 에어드롭이 가능한 경우이고, 점선은 거리는 전송이 가능하지만 버전이 호환되지 않는 경우를 나타낸다.
1 4 3 5 6 4 2 2 1 1
0