만타가오리

각 데이터 세트에서 너비 w인 입이 방향 alpha로 거리 t만큼 이동하며 쓸고 지나간 직사각형 안에 들어가는 플랑크톤의 개수를 센다.

보통5기하수학구현완전 탐색면접 대비아직 제출이 없습니다시간 제한2초메모리 제한512 MB

문제

만타가오리는 가장 큰 가오리로, 양쪽 지느러미를 편 길이가 20피트를 넘는다. 독침이 없고 사람을 해치지 않으며 헤엄치는 모습이 우아하다. 고래상어나 흰긴수염고래와 마찬가지로 만타가오리도 여과 섭식을 한다. 입을 벌린 채 헤엄치면 아가미가 체처럼 물속의 작은 플랑크톤을 걸러낸다.

만타가오리가 한 번 헤엄치는 동안 먹은 플랑크톤이 몇 개인지 세어라. 입의 너비, 헤엄치는 방향과 거리, 모든 플랑크톤의 위치가 주어진다.

만타가오리의 입은 길이가 ww 인 선분이고, 중점이 (x,y)(x, y) 에 있으며 헤엄치는 방향과 수직이다. 만타가오리가 방향 α\alpha 로 거리 tt 만큼 직진하면 입이 쓸고 지나간 자리는 두 변의 길이가 ttww 인 직사각형이 된다. 이 직사각형 내부에 있는 플랑크톤을 모두 먹는다.

입력

첫째 줄에 데이터 세트의 개수 KK 가 주어진다. K1K \ge 1 이다. 이어서 KK 개의 데이터 세트가 아래 형식으로 주어진다.

데이터 세트의 첫째 줄에는 여섯 개의 수 nn, xx, yy, ww, α\alpha, tt 가 주어진다. nn 은 정수이고 나머지는 모두 실수이다. nn 은 물속에 있는 플랑크톤의 개수이며 0n100000 \le n \le 10000 이다. (x,y)(x, y) 는 만타가오리 입 중점의 처음 위치이고, ww 는 입의 너비이다. α\alpha 는 헤엄치는 방향이며 양의 xx 축 방향에서 반시계 방향으로 잰 각으로 0α<2π0 \le \alpha < 2\pi 이다. tt 는 만타가오리가 헤엄치는 거리이며 0t10000 \le t \le 1000 이다.

다음 nn 개의 줄에는 각각 플랑크톤 하나의 좌표 xix_i, yiy_i 가 실수로 주어진다. 입력에 주어지는 플랑크톤은 입이 쓸고 지나간 직사각형의 경계 위에 놓이지 않는다.

출력

각 데이터 세트마다 먼저 Data Set x: 를 한 줄에 출력한다. 여기서 x 는 데이터 세트의 번호이며 1부터 센다. 다음 줄에 만타가오리가 이번 헤엄에서 먹은 플랑크톤의 개수를 출력한다. 각 데이터 세트 뒤에 빈 줄을 하나 출력한다.