문제
정올국에는 울타리가 쳐진 직사각형 모양의 공원이 있다.
나무와 사람들은 원 형태로 나타내어진다.
공원에는 각 꼭짓점마다 하나의 입구가 있다.
1번은 왼쪽 아래, 2번은 오른쪽 아래, 3번은 오른쪽 위, 4번은 왼쪽 위이다.
방문객들은 오직 입구만을 통해 출입할 수 있다.
방문객들은 해당 꼭짓점의 양 변에 닿았을 때 출입할 수 있다.
또한, 방문객들은 울타리와 나무에 겹치지 않는 한에서 공원 내에서 자유롭게 움직일 수 있다.
각 사람에 대하여, 들어가는 입구와 반지름이 주어졌을 때, 어떤 꼭짓점을 출구로 나갈 수 있는지 전부 구하여라.
27점 서브태스크에 대하여, 1 <= n <= 2000, m = 1이다. 31점 서브태스크에 대하여, 1 <= n <= 200, m = 100 000이다. 42점 서브태스크에 대하여, 1 <= n <= 2000, m = 100 000이다.
입력
첫 번째 줄에 나무의 수와 사람의 수인 n과 m이 공백으로 구분되어 주어진다.
두 번째 줄에 공원의 너비와 높이인 w와 h가 공백으로 구분되어 주어진다.
다음 줄부터 n줄에 걸쳐 각 나무의 x좌표, y좌표, 반지름이 공백으로 구분되어 주어진다.
다음 줄부터 m줄에 걸쳐 각 사람이 반지름과 들어오는 입구가 공백으로 구분되어 주어진다.
4k < w, h <= 10^9
출력
m개의 줄에 걸쳐, 각 사람이 나갈 수 있는 출구의 번호를 오름차순으로 정렬하여 공백 없이 출력하여라.
예제
5 3
16 11
11 8 1
6 10 1
7 3 2
10 4 1
15 5 1
1 1
2 2
2 1
1234
2
14
힌트
출처
BOI 2016
로그인해야 코드를 작성할 수 있어요.