만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

만타가오리

면접 대비

시간 제한2초메모리 제한512 MB

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

보통10점 중 5점

유형
기하, 수학, 구현, 완전 탐색
정답자
아직 제출이 없습니다

문제

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

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

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

입력

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

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

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

출력

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

예제5

  1. 예제 1

    입력
    1
    6 0.5 1.0 0.5 0.6 6.0
    1 1.8
    2 1.9
    1.5 3
    -2 -4
    5.4 4.05
    1 1.2
    
    예상 출력
    Data Set 1:
    3
    
  2. 예제 2

    입력
    1
    0 0.0 0.0 1.0 0.0 5.0
    
    예상 출력
    Data Set 1:
    0
    
    
  3. 예제 3

    입력
    1
    8 0.0 0.0 2.0 0.0 5.0
    0.1 0.9
    0.1 1.1
    4.9 -0.99
    5.1 0.0
    -0.1 0.0
    2.5 0.0
    2.5 -1.001
    0.001 0.999
    
    예상 출력
    Data Set 1:
    4
    
    
  4. 예제 4

    입력
    1
    6 3.0 2.0 1.0 3.14159265358979 3.0
    2.9 2.2
    0.1 1.6
    -0.1 2.0
    3.1 2.0
    1.5 2.6
    1.5 1.4
    
    예상 출력
    Data Set 1:
    2
    
    
  5. 예제 5

    입력
    1
    7 -1.0 -1.0 3.0 1.5707963267949 4.0
    -1.0 0.0
    0.4 2.9
    -2.6 0.0
    0.4 3.1
    -1.0 -1.1
    -2.4 2.5
    0.0 -0.5
    
    예상 출력
    Data Set 1:
    4