페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#8198
스페셜 저지
서브태스크
다국어

천문학자 (Astronomer) 5초 1024MB

문제

천문학자는 별 관측에 큰 열정을 가지고 있습니다. 특히 그는 망원경을 통해 동시에 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에 대한 최적의 해결책도 함께 표시되어 있습니다.


입력

첫 번째 줄은 네 개의 정수로 구성됩니다: 천문학자가 관측하고자 하는 별의 개수 k, 오늘 밤 하늘에 있는 별의 수 n, 이동 비용 s, 그리고 망원경 제작 비용 t. 그 다음으로 n개의 줄이 주어지며, 각 줄은 i번째 별의 정수 좌표 x_i와 y_i를 포함합니다.

  • 1\leq k\leq n\leq 700.

  • x_i, y_i\in \{-10^9,\ldots, 10^9\}, i\in\{1,\ldots,n\}.

  • s,t\in \{0,\ldots, 10^9\}.

  • 출력은 정확한 답과 상대적 또는 절대적 오차가 \epsilon = 10^{-6} 이내인 경우에만 허용됩니다.


출력

첫 줄에 천문학자가 지불해야 하는 최소 크로네 금액을 출력한다.


부분문제

번호 점수 조건
#18점

t \le s

#29점

n \le 50, s = 0

#318점

s=0

#413점

n \le 50

#514점

n \le 350

#615점

 \epsilon = 1/10

#723점

추가 제약 조건 없음


예제1

입력
231000500
00
20
31
출력
1000.0

예제2

입력
235003000
00
20
31
출력
3387.277541898787

예제3

입력
23250750
00
20
31
출력
1000.0

예제4

입력
230500
00
20
31
출력
353.5533905932738

예제5

입력
34010
00
100
510
55
출력
50.0

출처

BOI 2023

역링크