각 데이터 세트에서 너비 w인 입이 방향 alpha로 거리 t만큼 이동하며 쓸고 지나간 직사각형 안에 들어가는 플랑크톤의 개수를 센다.
보통5기하수학구현완전 탐색면접 대비아직 제출이 없습니다시간 제한2초메모리 제한512 MB만타가오리는 가장 큰 가오리로, 양쪽 지느러미를 편 길이가 20피트를 넘는다. 독침이 없고 사람을 해치지 않으며 헤엄치는 모습이 우아하다. 고래상어나 흰긴수염고래와 마찬가지로 만타가오리도 여과 섭식을 한다. 입을 벌린 채 헤엄치면 아가미가 체처럼 물속의 작은 플랑크톤을 걸러낸다.
만타가오리가 한 번 헤엄치는 동안 먹은 플랑크톤이 몇 개인지 세어라. 입의 너비, 헤엄치는 방향과 거리, 모든 플랑크톤의 위치가 주어진다.
만타가오리의 입은 길이가 w 인 선분이고, 중점이 (x,y) 에 있으며 헤엄치는 방향과 수직이다. 만타가오리가 방향 α 로 거리 t 만큼 직진하면 입이 쓸고 지나간 자리는 두 변의 길이가 t 와 w 인 직사각형이 된다. 이 직사각형 내부에 있는 플랑크톤을 모두 먹는다.
첫째 줄에 데이터 세트의 개수 K 가 주어진다. K≥1 이다. 이어서 K 개의 데이터 세트가 아래 형식으로 주어진다.
데이터 세트의 첫째 줄에는 여섯 개의 수 n, x, y, w, α, t 가 주어진다. n 은 정수이고 나머지는 모두 실수이다. n 은 물속에 있는 플랑크톤의 개수이며 0≤n≤10000 이다. (x,y) 는 만타가오리 입 중점의 처음 위치이고, w 는 입의 너비이다. α 는 헤엄치는 방향이며 양의 x 축 방향에서 반시계 방향으로 잰 각으로 0≤α<2π 이다. t 는 만타가오리가 헤엄치는 거리이며 0≤t≤1000 이다.
다음 n 개의 줄에는 각각 플랑크톤 하나의 좌표 xi, yi 가 실수로 주어진다. 입력에 주어지는 플랑크톤은 입이 쓸고 지나간 직사각형의 경계 위에 놓이지 않는다.
각 데이터 세트마다 먼저 Data Set x: 를 한 줄에 출력한다. 여기서 x 는 데이터 세트의 번호이며 1부터 센다. 다음 줄에 만타가오리가 이번 헤엄에서 먹은 플랑크톤의 개수를 출력한다. 각 데이터 세트 뒤에 빈 줄을 하나 출력한다.