레이팅 미적용알다시피 올해 러시아에서 열리는 주요 스포츠 행사는 ACM ICPC만이 아니다. 몇 달 전 예카테린부르크에서 약 3 000 km 떨어진 소치에서 2014 동계 올림픽이 열렸다. 점점 더 많은 종목에서 경기의 승자를 결정하는 것은 선수의 능력만이 아니라 장비이기도 하다. 예를 들어 활강 스키에서는 최신 스키 기술 덕분에 선수들이 속도를 높이고 회전 능력을 개선할 수 있다. 당신은 최신 스키 기술이 활강 코스를 주파하는 스키 선수의 능력에 미치는 영향을 알아보는 일을 맡았다. 코스에는 여러 목표 지점이 있고, 스키 선수는 가능한 한 많은 지점을 지나가고 싶어 한다. 당연히 스키 기술이 좋을수록 이 일은 쉬워진다. 단순화를 위해 스키 선수가 위치 (0,0)에서 출발하고 “내리막”이 양의 \(y-ax\)is 방향에 해당하는 2차원(t\(wo-di\)mensional) 좌표계를 사용한다. 선수 속도의 y 성분(\(y-co\)mponent)은 상수 \(vy\)라고 가정한다. 선수는 옆 방향(\(x-di\)rection)으로는 속도를 바꿀 수 있지만, 스키 장비의 한계로 옆 방향 가속도는 최대 \(a\)max이다. 선수는 옆 방향 속도 0으로 출발한다. (0,0) x y Skier’s path 그림 J.1: 세 개의 목표 지점을 지나는 활강 스키 경로 그림 J.1(첫 번째 샘플 입력에 해당)에서 최적 경로는 가능한 네 목표 지점 중 세 개를 지난다. \(a\)max가 더 작았다면 선수는 두 개 이하의 목표 지점만 지날 수 있었을지도 모른다.
입력은 하나의 테스트 케이스로 이루어져 있다. 첫 줄에는 세 정수 \(n\), \(vy\), \(a\)max (\(0 \le n \le 250\), \(0 \le vy \le 10^{5}\), \(0 \le a\)m\(ax \le 10^{7}\))가 주어지며, \(n\)은 목표 지점의 수, \(vy\)는 선수 속도의 y 성분(\(y-co\)mponent), \(a\)max는 최대 옆 방향 가속도이다. 여기서 \(vy\)는 시간당 미터, \(a\)max는 시간 제곱당 미터 단위이다. 이어서 \(n\)개의 줄에 각각 두 정수 \(xi\)와 \(yi\) (−\(10^{5} \le xi\), y\(i \le 10^{5}\))가 주어진다. 이는 코스에서 방문할 각 목표 지점의 좌표이다. 모든 좌표는 미터 단위이다. 목표 지점은 주어진 순서대로 1, 2, ..., \(n\)으로 번호가 매겨진다.
선수가 한 번의 활주로 코스에서 지나갈 수 있는 최대 길이(maxim\(al-le\)ngth)의 목표 지점 수열을 출력한다. 지나는 순서대로 목표 지점을 출력한다. 최대 길이(maxim\(al-le\)ngth) 수열이 여러 개면 사전순으로 가장 앞서는 것만 출력한다. (따라서 수열 2 15가 수열 10 15보다 앞선다.) 선수가 아무 목표 지점도 지날 수 없으면 대신 Cannot visit any targets를 출력한다. 부동소수점(floati\(ng-po\)int) 안정성을 위해, \(a\)max를 0.1까지 흔들어도 답이 변하지 않는다고 가정해도 된다.
4 100 400
-100 100
50 200
-100 300
150 300
1 2 4
1 100 100
1000 10
Cannot visit any targets