볼록 껍질의 꼭짓점 수와 넓이
레벨 E3 · 코딩 · JavaScript · 목표 시간 37분 · 게시일 2026-11-03
평면 위 정수 좌표 점 배열 points([x, y])가 주어진다. 모든 점을 감싸는 가장 작은 볼록 다각형(볼록 껍질)을 생각한다. [꼭짓점 수, 넓이의 2배]를 구하시오. 껍질의 변 위에 놓였을 뿐 꺾이지 않는 점은 꼭짓점으로 세지 않는다. 넓이의 2배는 항상 정수이다.
점은 3개 이상 100,000개 이하이고 모두 한 직선 위에 있지는 않다. 같은 점이 여러 번 나올 수 있다. 좌표의 절댓값은 10^7 이하이다. 꼭짓점이 매우 많은 경우도 있어서, 꼭짓점마다 모든 점을 훑는 방법으로는 시간 안에 끝나지 않는다.
예제
solve([[0,0],[4,0],[4,4],[0,4],[2,2],[2,0]]) solve([[0,0],[1,0],[0,1]]) solve([[0,0],[3,1],[1,3],[3,1],[1,1]])