8068 : 볼록 껍질
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
2차원 평면 위에 $N$개의 점이 주어졌을 때, 이 점들을 모두 포함하는 가장 작은 볼록 다각형인 볼록 껍질(Convex Hull)을 구하는 프로그램을 작성하십시오.
[제약 조건]
• $3 \le N \le 30{,}000$
• 모든 좌표값의 절댓값 $\le 10^9$
[제약 조건]
• $3 \le N \le 30{,}000$
• 모든 좌표값의 절댓값 $\le 10^9$
입력 설명
첫째 줄에 점의 개수 $N$이 주어집니다. ($3 \le N \le 30{,}000$)
둘째 줄부터 $N$개의 줄에 걸쳐 각 점의 좌표를 나타내는 두 정수 $x_i, y_i$가 한 줄에 하나씩 주어집니다.
모든 좌표값의 절댓값은 $10^9$ 이하이며, 동일한 위치에 여러 점이 주어질 수 있습니다.
둘째 줄부터 $N$개의 줄에 걸쳐 각 점의 좌표를 나타내는 두 정수 $x_i, y_i$가 한 줄에 하나씩 주어집니다.
모든 좌표값의 절댓값은 $10^9$ 이하이며, 동일한 위치에 여러 점이 주어질 수 있습니다.
출력 설명
첫째 줄에 볼록 껍질을 구성하는 꼭짓점의 개수 $H$를 출력합니다.
둘째 줄부터 $H$개의 줄에 걸쳐 볼록 껍질을 이루는 꼭짓점들의 좌표 $x, y$를 한 줄에 하나씩 반시계 방향 순서로 출력합니다.
단, 시작점은 $y$좌표가 가장 작고, $y$좌표가 같은 꼭짓점이 여러 개라면 그 중 $x$좌표가 가장 작은 점이어야 합니다.
볼록 껍질의 세 점이 일직선을 이루는 경우, 중간에 위치한 점은 꼭짓점에서 제외하고 오직 양 끝점만 출력합니다.
둘째 줄부터 $H$개의 줄에 걸쳐 볼록 껍질을 이루는 꼭짓점들의 좌표 $x, y$를 한 줄에 하나씩 반시계 방향 순서로 출력합니다.
단, 시작점은 $y$좌표가 가장 작고, $y$좌표가 같은 꼭짓점이 여러 개라면 그 중 $x$좌표가 가장 작은 점이어야 합니다.
볼록 껍질의 세 점이 일직선을 이루는 경우, 중간에 위치한 점은 꼭짓점에서 제외하고 오직 양 끝점만 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
8
1 1
1 2
2 2
2 1
0 0
0 3
3 3
3 0
출력 예시
COPY
복사되었습니다!
복사되었습니다!
4
0 0
3 0
3 3
0 3도움
모노톤 체인(Monotone Chain) 알고리즘이나 그레이엄 스캔(Graham Scan)을 사용하여 $O(N \log N)$에 볼록 껍질을 찾습니다.
일직선 상의 점 제거 조건(CCW가 0인 상태) 및 반시계 방향 정렬 기준점 재배치 조건을 엄격하게 적용하여 구현합니다.
일직선 상의 점 제거 조건(CCW가 0인 상태) 및 반시계 방향 정렬 기준점 재배치 조건을 엄격하게 적용하여 구현합니다.