1177번 - 조쌤포스 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 128 MB | 309 | 72 | 57 | 22.093% |
문제
학생들은 프로그래밍 시간에 계속해서 떠들고 있다. 더 이상 참지 못한 조쌤은 자리를 박차고 애들을 잡기 위해 뛰기 시작했고 이와 동시에 떠들던 $N$명의 학생은 도망가기 시작했다.
현재 조쌤은 $(B_X, B_Y)$ 위치에 있다. 그리고 뛰기 시작한 조쌤은 $t$초 후 $(B_X+BV_X \times t, B_Y+BV_Y \times t)$ 위치에 있게 된다. 즉, 조쌤은 초당 $(BV_X, BV_Y)$ 방향으로 뛰고 있는 것이다.
$N$명의 학생 역시 현재 $(X_i, Y_i)$에 위치하고 있고 $t$ ($t ≥ 0$)초 후 $(X_i+VX_i \times t, Y_i+VY_i \times t)$ 위치에 있게 된다.
조쌤은 현재 자신 위치에서 반경이 $R$인 원 안에 있는 아이들은 모조리 잡을 수 있다. 하지만 위의 조건을 살펴보면 현재 아이들과 조쌤 모두 뛰는 상황이기에 시간마다 아이들을 잡을 수 있는 숫자가 변한다. 조쌤은 한 번 잡고나면 잡히지 않은 아이들은 모두 도망간 상태기 때문에 단 한번의 기회에 최대한 많은 아이들을 잡고 싶다.
문제는 조쌤과 학생들의 위치 및 뛰는 방향이 주어지면 한 번에 얼마나 많은 학생을 잡을 수 있는지 구하는 것이다. 물론, 최대한 많이 잡을 수 있는 시간이 정수가 아닌 소수일 수도 있다.
입력
첫 줄에는 학생의 수 $N$과 조쌤이 잡을 수 있는 반경 $R$, 그리고 조쌤의 위치를 나타내는 $B_X$, $B_Y$와 조쌤이 뛰는 방향을 나타내는 $BV_X$, $BV_Y$가 공백으로 구분되어 주어진다. 두 번째 줄부터 $N+1$번째 줄까지는 각 학생의 정보가 주어지는데 각 줄에는 학생의 초기 위치 $X_i$, $Y_i$와 뛰는 방향 $VX_i$, $VY_i$가 공백으로 구분되어 주어진다.
출력
첫 줄에 조쌤이 한 번에 잡을 수 있는 최대 학생 숫자를 출력한다. 실수 오차 조정을 위해 학생과 조쌤 사이의 거리가 $R \pm 0.0001$이라면 잡을 수 있다고 한다.
제한
- $1 ≤ N ≤ 50\,000$
- $1 ≤ R ≤ 2\,500$
- $-1\,000 ≤ B_X, B_Y ≤ 1\,000$
- $-100 ≤ BV_X, BV_Y ≤ 100$
- $-1\,000 ≤ X_i, Y_i, VX_i, VY_i ≤ 1\,000$
- 입력되는 모든 수는 정수
예제 입력 1
3 1 0 0 0 2 0 -3 0 4 1 2 -1 1 1 -2 2 -1
예제 출력 1
2
힌트
$1.5$초의 시간이 흐른 후 조쌤은 $(0, 3)$에 위치해 있고 각 학생은 $(0, 3)$, $(-0.5, 3.5)$, $(4, -3.5)$에 위치하여 있다. 즉 반경 $1$ 안에 있는 $1$, $2$번 학생을 조쌤은 잡을 수 있고 이것이 한 번에 잡을 수 있는 최대 학생 수가 된다.
출처
Olympiad > USA Computing Olympiad > 2008-2009 Season > USACO Holiday Bonus 2009 Contest > Gold 1번
- 문제를 번역한 사람: author6
- 문제의 오타를 찾은 사람: luciaholic
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호