측량 표지
골드 I의견: 0
측량팀이 평면 위에서 \(N\)개의 측량 표지를 설치했다. 각 표지의 좌표는 정수이다. 이 표지들을 모두 안쪽(경계 포함)에 담는 가장 작은 볼록 다각형, 즉 볼록 껍질의 꼭짓점이 몇 개인지를 구하려고 한다.
볼록 껍질의 변 위에 놓여 있지만 꺾이는 지점이 아닌 점(같은 변 위의 중간 점)은 꼭짓점으로 세지 않는다. 즉, 볼록 껍질의 경계에서 실제로 방향이 바뀌는 점의 개수만 센다.
단, 모든 표지가 한 직선 위에 있어 볼록 다각형을 만들 수 없는 경우, 서로 다른 점이 하나뿐이면 \(1\)을, 그 외에는 \(2\)를 출력한다(직선의 양 끝점).
\(1 \le N \le 100\,000\)
\(-10^9 \le x, y \le 10^9\)
첫째 줄에 표지의 개수 \(N\)이 주어진다.
다음 \(N\)개의 줄에 각각 표지의 좌표 \(x\), \(y\)가 주어진다. 같은 좌표가 여러 번 주어질 수 있다.
볼록 껍질의 꼭짓점 개수를 한 줄에 출력한다.
5
0 0
2 0
2 2
0 2
1 14정사각형의 네 꼭짓점이 껍질을 이루고, 가운데 점 \((1,1)\)은 내부에 있다. 답은 \(4\).
3
0 0
1 1
2 22세 점이 모두 한 직선 위에 있으므로 볼록 다각형을 만들 수 없고, 양 끝점만 남아 답은 \(2\).
막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
riseoj 작성
출처 Original
평가 및 의견
측량 표지
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
측량 표지