페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
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

입력
2 3 1000 500
0 0
2 0
3 1
출력
1000.0

예제2

입력
2 3 500 3000
0 0
2 0
3 1
출력
3387.277541898787

예제3

입력
2 3 250 750
0 0
2 0
3 1
출력
1000.0

예제4

입력
2 3 0 500
0 0
2 0
3 1
출력
353.5533905932738

예제5

입력
3 4 0 10
0 0
10 0
5 10
5 5
출력
50.0

출처

BOI 2023

역링크 공식 문제집만