탐험대 울타리
골드 V의견: 0
오지 탐험대가 지도 위에 \(N\)개의 베이스캠프 위치를 표시했다. 대원들은 모든 베이스캠프를 내부에 포함하거나 경계 위에 놓이도록 울타리를 치려 한다. 울타리의 모양은 볼록 다각형 이어야 하며, 그 둘레를 최소화하고 싶다.
최소 볼록 울타리의 둘레 길이를 구하여라. 모든 베이스캠프가 한 점에 모여 있거나 한 직선 위에 있는 경우도 입력될 수 있다.
- \(1 \le N \le 200\,000\)
- \(-10^8 \le x_i, y_i \le 10^8\)
- 좌표는 정수이다.
첫째 줄에 베이스캠프의 수 \(N\)이 주어진다.
다음 \(N\)개의 줄에 걸쳐 베이스캠프의 좌표 \((x_i, y_i)\)가 공백으로 구분되어 주어진다.
최소 볼록 울타리의 둘레 길이를 소수점 여섯째 자리까지 출력한다. 오차는 \(10^{-4}\) 이하이면 정답으로 인정한다.
5
0 0
4 0
4 4
0 4
2 2
16.000000
주어진 \(5\)개의 점 중 \((2, 2)\)는 볼록 껍질 내부에 있다. 볼록 껍질은 정사각형 \((0,0)-(4,0)-(4,4)-(0,4)\)이며 둘레는 \(4 \times 4 = 16.000000\)이다.
3
0 0
6 0
3 4
16.000000
세 꼭짓점 \((0,0)\), \((6,0)\), \((3,4)\)가 볼록 껍질을 이룬다. 변의 길이는 \(6\), \(5\), \(5\)이므로 둘레는 \(16.000000\)이다.
막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
riseoj 작성
출처 Original
평가 및 의견
탐험대 울타리
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
탐험대 울타리