목장 울타리 치기
골드 I의견: 0
목장에 말뚝 \(N\)개가 박혀 있다. 동물 보호 규정에 따라, 울타리는 모든 말뚝에서 거리 \(L\) 이상 떨어지도록 설치해야 한다.
이 조건을 만족하는 가장 짧은 닫힌 울타리의 길이를 구하라. 최적의 울타리는 말뚝들의 볼록 껍질을 거리 \(L\)만큼 부풀린 모양이 된다: 직선 구간들의 길이 합은 볼록 껍질의 둘레와 같고, 꼭짓점마다 생기는 호를 모두 이으면 반지름 \(L\)인 원 하나가 된다.
- \(1 \le N \le 100{,}000\)
- \(1 \le L \le 10^4\)
- \(-10^4 \le x, y \le 10^4\)
첫째 줄에 말뚝의 수 \(N\)과 거리 \(L\)이 주어진다.
다음 \(N\)개의 줄에 각 말뚝의 정수 좌표 \(x\ y\)가 주어진다 (같은 좌표가 여러 번 주어질 수 있다).
울타리의 최소 길이를 소수점 아래 넷째 자리까지 출력한다. 절대오차 또는 상대오차 \(10^{-4}\) 까지 정답으로 인정한다.
4 1
0 0
0 3
4 0
4 320.2832직사각형 둘레 \(14\)에 반지름 \(1\)인 원둘레 \(2\pi\)를 더해 \(14 + 2\pi \approx 20.2832\)가 된다.
1 5
2 231.4159말뚝이 하나뿐이면 울타리는 반지름 \(5\)인 원이므로 길이는 \(10\pi \approx 31.4159\)이다.
막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
riseoj 작성
출처 Original
평가 및 의견
목장 울타리 치기
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
목장 울타리 치기