(x,y)에서 (0,0)으로 갈 때
<rule>
1. 1초당 1 (이 경우 거리가 0.5 남으면 0.5초 걸린다)
2. 정확히 T초당 D (0.5T만큼 움직여서 0.5D만큼 움직이는건 불가능하다)
두가지 방법이 있을 때 집까지 가는 최단시간을 구하는 문제다.
T<D일 때 원을 계속 확장시킨다는 이미지로 생각하면 편하다.
<way>
1. T>=D라면 초당 1씩 가는것보다 절대 빠를 수 없으므로 sqrt(x^2,y^2)를 출력.
2. 원의 반지름을 D씩 점점 확장시켜 본다.
(1) 반지름이 D일 때. 이 때는 정확히 D 거리의 점만 커버한다.
(2) n*D일 때. (n+1)*D 이내의 모든 면적을 커버한다.
3. way.2를 따라 원을 확장시켰을 때 가장자리에서 1번 방법을 통해 0,0으로 가는게 빠른지, 2번 방법을 통해 가는게 빠른지 비교하여 작은 값을 택한다.
간단한 TC
0 5 3 1
AC = 2
WA = 3
<코드>
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 | #include <stdio.h> #include <iostream> #include <algorithm> using namespace std; typedef double db; db x, y, d, t; db solve() { db target = sqrt(x*x + y*y); if (d <= t) return target; db ti = target, a = 0; while (1) { target -= d; a += t; if (a + abs(target) > ti) break; ti = min(ti, a + abs(target)); } target = sqrt(x*x + y*y); for (db i = 1; i <= target; i++) { if (target > (i - 1)*d && target <= (i + 1)*d) ti = min(ti, (i + 1)*t); } return ti; } int main() { cin >> x >> y >> d >> t; printf("%.13lf\n", solve()); return 0; } | cs |
'BOJ' 카테고리의 다른 글
| 14619 섬 여행 (0) | 2017.08.30 |
|---|---|
| 11664 선분과 점 (0) | 2017.08.30 |
| 2570 비숍 (0) | 2017.08.30 |
| 2316 도시 왕복하기 (0) | 2017.08.30 |
| 14671 영정이의 청소 (0) | 2017.08.30 |