시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 21 | 9 | 8 | 72.727% |
상근이는 대서양 해안에 살고 있다. 어느 날 하늘을 쳐다보니 보름달이 떠 있었다. 보름달 일 때는 간만의 차가 커진다. 상근이는 비가 오지 않는 날을 선택해 해안선을 산책하려고 한다.
해안선을 산책하다가 밀물을 만나면 바닷물에 갇힐 수 있다. 따라서, 조류를 잘 살펴본 뒤에 산책 계획을 세워야 한다.
안전하게 산책을 하려면 간조일 때 산책을 하면 된다. 하지만, 문제는 이 해안이 돌로 이루어져 있다는 점이다. 돌에서 미끄러지면 다칠 수 있기 때문에, 상근이는 돌이 한 시간 전에 마른 상태가 되어야 돌 위로 올라갈 수 있다.
해변은 거의 대부분이 모래로 이루어져 있고, 그 위에 돌이 놓여져 있는 형태이다. 모든 구역은 마른 상태이거나 물에 잠겨있는 상태이다. 구역의 높이보다 물의 높이가 높아진 순간에 구역은 물에 잠기며, 인접한 구역의 높이와는 관계 없다.
해변은 10 × 10m 단위로 구역을 나눌 수 있고, 각 구역의 높이는 모두 알고 있다. 각 정사각형에 들어가려면, 인접한 네 정사각형에서 이동해야 한다. 또, 두 구역의 높이가 \(z_1\), \(z_2\)라고 할 때, 높이의 차이 \(\left| z_1 - z_2 \right| \)가 최대 1m인 경우에만 이동할 수 있다.
한 정사각형에서 다른 정사각형으로 갈 때, 걸리는 시간은 일정하며, 이 시간 동안 두 정사각형은 모두 마른 상태이어야 한다.
해수면의 높이는 여러 가지 요인에 의해 결정된다. 상근이는 물의 높이 \(v\)(미터)가 만조로 부터 지난 시간 \(t\)(시간)와 여러 가지 요인에 의해 결졍된 높이 \(a\)(미터)로 다음과 같이 나타낼 수 있다는 사실을 알게 되었다.
\[v=0.5a \cdot (\cos { (t \frac{2 \pi}{12}) } + 1 )\]
상근이는 산책을 집에서 시작하고, 집에서 끝내려고 한다. 밀물이 몰려오기 전 까지 시간이 얼마 남지 않았기 때문에 0.0 ≤ t ≤ 12.0 시간 안에 산책을 마치려고 한다. 상근이는 얼마나 멀리 산책하러 나갈 수 있을까?
첫째 줄에 두 실수 \(a\) (0.0 < \(a\) < 15.0) 과 한 정사각형을 지나가는데 걸리는 시간 \(m\) (0.1 ≤ \(m\) ≤ 60.0)이 주어진다. \(m\)의 단위는 초이다.
둘째 줄에는 네 정수 \(W\), \(H\), \(X\), \(Y\)이 주어진다. (1 ≤ \(W\),\(H\) ≤ 200, 0 ≤ \(X\) < \(W\), 0 ≤ \(Y\) < \(H\)) \(W\)와 \(H\)는 지도의 너비와 높이이고, \(X\)와 \(Y\)는 상근이의 집의 좌표 (\(X\),\(Y\)) 이다.
다음 \(H\)개 줄에는 \(W\)개의 정수가 공백으로 구분되어져서 주어진다. 각 정수는 각 10 × 10m 단위 정사각형의 높이이며, 가장 해수면의 높이가 낮았을 때가 기준이다. 단위는 밀리미터이다. 각 정사각형의 높이는 0보다 크며, 20,000을 넘지 않는다. 첫째 줄의 첫 번째 숫자가 (0,0)에 해당하며, 상근이의 집은 항상 마른 상태이다.
첫째 줄에 상근이가 가장 멀리 갈 수 있는 곳과의 유클리드 거리를 출력한다. 두 정사각형 사이의 거리는 두 중심 사이의 거리로 계산할 수 있다. 상대/절대 오차가 10-6 이내인 경우에만 정답이다.
소수점 계산으로 생기는 오차를 막기 위해서 걷는 속도 \(0.999m\) < \(m' \) < \(1.001m\)인 \(m'\)인 경우에 정답과 같다.
2.0 10.0 3 3 0 0 2001 1000 100 1001 10000 200 100 0 0
20
4.0 30.0 6 2 2 0 73 1001 4001 1001 76 70 70 2001 3001 2001 72 71
22.36067977
ICPC > Regionals > Europe > Northwestern European Regional Contest > Nordic Collegiate Programming Contest > NCPC 2013 K번