천문학자는 별 관측에 큰 열정을 가지고 있습니다. 특히 그는 망원경을 통해 동시에 k개의 별을 관측하는 데 큰 즐거움을 느낍니다. 반지름이 r인 망원경을 만드는 비용은 t\cdot r 크로네입니다. 새로 만든 망원경은 정확히 원점 (0,0)을 향하게 됩니다. 다른 곳을 향하게 하려면 이동 비용이 발생하며, 망원경을 d만큼 이동시키는 비용은 s\cdot d 크로네입니다. 천문학자는 망원경이 향하는 곳에서 최대 반지름 r 내에 있는 모든 별을 관측할 수 있습니다.

k개의 별을 동시에 관측할 수 있는 망원경을 만들고 이동시키는 데 드는 비용은 얼마일까요?

모든 좌표와 거리는 유클리드 평면에서 주어집니다.

다음은 n=3개의 별이 (0,0), (2,0), (3,1)에 위치한 예시입니다. 그림에서 음영이 칠해진 영역은 반지름 1인 망원경이 (1,0)을 향하고 있으며, 이 망원경은 두 개의 별을 포함하고 있습니다. 이 비용은 s + t 크로네로, 샘플 입력 3에 대한 최적의 해결책입니다. 이미지에는 샘플 입력 1, 2, 4에 대한 최적의 해결책도 함께 표시되어 있습니다.

#8198 upload 1 done - how_to_reg - auto_awesome スペシャルジャッジ call_split サブタスク

천문학자 (Astronomer) timer 5s memory 1024MB

#8198
スペシャルジャッジ

サブタスク

천문학자 (Astronomer) 5s 1024MB