목록convex hull (1)

마이 플밍 블로그

[C++]백준 1708 - 볼록 껍질

https://www.acmicpc.net/problem/1708 1708번: 볼록 껍질 첫째 줄에 점의 개수 N(3 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 점의 x좌표와 y좌표가 빈 칸을 사이에 두고 주어진다. 주어지는 모든 점의 좌표는 다르다. x좌표와 y좌표의 범 www.acmicpc.net 문제에선 Convex Hull에 대한 설명을 하는데 Convex Hull이란 가장 바깥쪽에 있는 정점들을 이어서 만드는 볼록 다각형을 뜻한다. 이런 Convex Hull을 만드는 알고리즘 중에서는 Graham's Scan 알고리즘이 있다. 이 문제는 Graham's Scan 알고리즘으로 풀었는데 이 알고리즘에 대해 설명하자면먼제 Convex Hull을 자세히보면 이어진 정점들이..
문제풀이/백준 2022. 3. 15. 03:44
이전 Prev 1 Next 다음