BOJ 13957 Within Arm's Reach

먼저, 최종적으로 닿는 좌표는 $n$개의 선분이 만드는 $n$개의 벡터의 합이므로, 길이들을 적절히 재배열해서 각각의 벡터를 구한 다음 원래의 순서로 재배열하여 누적 벡터 합을 출력하면 됩니다.

엣지 케이스는 다음과 같은 경우가 있습니다.

• 모든 $l_i$의 합보다 목적지가 멀리 있는 경우, 모든 벡터를 목적지 방향으로 뻗는 것이 최적입니다.
• 모든 $l_i$ 중에서 가장 긴 것을 $l_{max}$라고 하고, 그 외의 $l_i$들의 합을 $l_{rest}$라고 합시다. 이때 $l_{max} > l_{rest}$이면, 원점에서 $l_{max} - l_{rest}$ 보다 가까운 점에는 닿을 수 없습니다. 이때는 $l_{max}$를 목적지 방향으로 뻗고 나머지를 원점으로 돌아오는 방향으로 설정하는 것이 최적입니다.

그 외의 모든 경우에는 목적지에 정확히 닿을 수 있습니다. 원점에서 목적지까지의 거리를 $d$라고 합시다.

• $l_{max} > l_{rest}$이면서 닿을 수 있는 경우는 거리가 $l_{max} - l_{rest}$ 이상, $l_{max} + l_{rest}$ 이하입니다. 이때는 $(d, l_{max}, l_{rest})$가 삼각형을 이룰 수 있습니다. (degenerate 삼각형 포함) 삼각형의 세 변의 길이가 주어질 때 내각은 코사인 제2법칙을 이용하여 구할 수 있습니다. 이는 degenerate 삼각형에서도 통하지만 실수 오차로 인해 NaN이 나올 수 있으므로, 변의 길이를 $0.001$ 정도 조절하여 확실하게 삼각형이 되도록 하여 구하는 것이 좋습니다.
• $l_{max} \le l_{rest}$인 경우는 $d > l_{max}$인 경우와 아닌 경우로 나눕니다.
  • $d > l_{max}$라면, $l_{max}$를 포함한 모든 변들을 적절히 두 개의 집합으로 나눠서 두 길이의 합의 차이가 $l_{max}$ 이하가 되게 만들 수 있습니다. $n \le 20$이므로 적당한 분할을 브루트포스로 구해 줍니다. 그러면 $d$와 두 개의 합은 삼각형을 이룹니다.
  • $d \le l_{max}$라면, 먼저 $l_{max}$ 하나를 이용하여 $(x, y)$에서 정확히 $l_{max}$만큼 떨어진 점으로 이동합니다. 그 뒤에 $l_{rest}$를 마찬가지로 차이 $l_{max}$ 이하인 두 집합으로 분할하여 목적지로 이동합니다.