측량 부지의 둘레
골드 II의견: 0
드론으로 부지를 측량했더니 말뚝 \(N\)개의 좌표가 얻어졌다. 그런데 전송 과정에서 좌표가 뒤죽박죽 섞여서, 어떤 순서가 부지의 경계인지 알 수 없게 되었다.
모든 말뚝을 둘러싸는 가장 짧은 닫힌 울타리의 길이를 구하라. (같은 좌표가 여러 번 주어질 수 있다. 모든 말뚝이 한 직선 위에 있다면, 닫힌 울타리는 그 선분을 따라 왕복해야 하므로 길이는 선분 길이의 \(2\)배이다.)
\(3 \le N \le 100{,}000\), \(|x|,|y| \le 10^9\)
첫 줄에 말뚝 수 \(N\) 이 주어집니다.
이어 \(N\) 개의 줄에 말뚝 좌표 \(x\ y\) 가 임의의 순서로 주어집니다.
울타리의 최소 길이를 소수점 아래 넷째 자리까지 출력합니다. 절대오차 또는 상대오차 \(10^{-4}\) 까지 정답으로 인정합니다.
6
3 4
0 0
3 0
1 1
0 4
2 314.0000바깥쪽 네 말뚝 \((0,0),(3,0),(3,4),(0,4)\)를 두르는 직사각형 울타리 길이 \(2\times(3+4)=14\)가 최소이다.
5
0 3
4 0
2 1
0 0
1 112.0000빗변이 \(5\)인 직각삼각형 \((0,0),(4,0),(0,3)\) 둘레 \(3+4+5=12\)가 답이다. 안쪽 말뚝은 울타리에 영향을 주지 않는다.
막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
riseoj 작성
출처 Original
평가 및 의견
측량 부지의 둘레
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
측량 부지의 둘레