시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 37 | 5 | 5 | 18.519% |
게임 개발자인 은기는 Angry Bird와 Flappy Bird 를 능가하는 새로운 게임을 개발하기로 했다. 바로 ALPS(Angry Larva, Punish Snakes) 이다. 우리는 카와이한 라바를 던져서 뱀들을 쓰러트려야 한다.
라바의 발사지점은 (0,0)이고, 초기속력(속도가 아니다)은 V0 m/s로 정해져있고, 중력가속도 g = 10m/s^2이다. 이 게임에서 우리는 라바를 크기가 0인 점으로, 필드에 있는 뱀들을 y축과 평행한 선분으로 모델링할 수 있다. 아직 개발단계이기 때문에 공기마찰과 뱀과 충돌했을 때의 속도변화는 고려하지 않는 상황이다.
뱀을 맞췄다는 것은 선분 사이로 라바가 지나갔다는 것이고, 이 경우 1점을 얻게된다. 은기는 이 ALPS 게임의 스테이지를 만들어둔 상태다. 그러다가 각 스테이지에서 얻을 수 있는 점수의 최댓값이 궁금해졌다. 현재 스테이지의 초기속력 V0와 뱀들의 위치가 주어졌을 때, 이 스테이지에서 얻을 수 있는 최고점수를 구해보자.
첫 째 줄엔 테스트케이스의 개수 t (0 < t ≤ 10) 가 주어진다. 이후 각 테스트케이스에 대해 아래와 같은 정보가 주어진다.
각 테스트케이스마다 첫 번째 줄에는 초기속력 V0 (0 < V0 ≤ 1000) 와 뱀의 수 n (0 < n ≤ 20,000) 두개의 정수가 주어진다.
그 다음 n개의 줄에 걸쳐서 뱀의 정보가 세 개의 정수로 주어진다. 이 수들은 뱀의 x좌표 (0 < x ≤ 10,000) 와 뱀의 양 끝점의 y좌표 (0 < y1 ≤ y2 ≤ 10,000) 이다.
각 테스트케이스마다 얻을 수 있는 점수의 최댓값을 한줄씩 출력한다.
3 10 2 3 1 2 3 2 3 10 3 1 1 1 2 2 3 3 4 6 10 3 1 1 2 2 3 4 3 5 6
2 1 2