====== 볼록 껍질 (Convex Hull) ====== * 난이도: 플래티넘 5 * 기본 문제: [[ps:problems:boj:1708]] * 참고 자료 * [[https://cp-algorithms.com/geometry/convex-hull.html]] ===== 개요 ===== * 정의는 '모든 점을 포함하는 가장 작은 볼록다각형' 이다. * 작다는 것은, 면적을 기준으로 해도 되고, 둘레의 길이를 기준으로 해도 된다. * 문제에서 주어지는 다른 표현들로는 이런 것들이 있다. * 임의의 점 3개로 만들어지는 삼각형들의 합집합 * * 최적 시간 복잡도는 O(nlogn). O(nlogh)도 있긴 하지만.. * 널리 알려진 O(nlogn) 알고리즘 은 두가지이다. * Graham scan 과 monotone chain * 더 널리 알려진것? 은 Graham scan 이다 * 바닥상태에서 짜기 쉬운 것은 monotone chain이다. Graham scan은 점들의 각도정렬을 할줄 알아야 한다. * 속도는.. * Graham scan의 각도 정렬을 ccw를 써서 하면 monotone chain보다 느리다 * Graham scan의 각도 정렬을 x/y 값을 사용하고, 최적화하면 monotone chain보다 빨라진다 * monotone chain은 upper hull과 lower hull을 각각 계산하기 위해서 모든 점을 이터레이션 하는 것을 두번 반복해야 하는데, Graham scan은 한번으로 된다. ===== 구현 ===== * Monotone Chain 의 * Graham Scan ==== Graham Scan ==== * 각도 정렬을 시킬때, 각도로만 정렬하는 방법과 (각도, 거리)으로 정렬하는 방법(각도가 같을때는 거리가 짧은것이 앞서도록) 이 있다. * 기본적으로는 각도로만 정렬해도 충분하지만, 이 때에는 가장 작은 각도에 해당되는 점과 가장 큰 각도에 해당되는 점이 여러개일경우를 따로 처리해줘야 한다. * 가장 작은 각도에 해당되는 점들 중에서는 거리가 가장 큰 점을 선택해야 한다. * 만약 3개 이상이 점이 한 직선상에 있는 경우를 모두 볼록껍질에 포함시키기로 결정했다면, 이 점들을 거리순으로 정렬해야 한다. * * (각도, 거리)로 정렬하는 것은 가장 작은 각도에 해당되는 점과 가장 큰 각도에 해당되는 점이 여러개일때, 이것들을 ==== 예외 처리 ==== * 같은 점이 두개 이상 있는 경우? * 이걸 허용하면 골치아프다. 허용하지 말자 * 3개 이상이 점이 한 직선상에 있는 경우? * 이건 처리해줘야 한다. 모든 점을 볼록껍질에 포함시킬건지, 양 끝점만 볼록껍질에 포함시킬건지를 결정해야 한다. * 모든 점이 한 직선상에 있는 경우? * 예외 취급 해야하나? 응 * ===== 관련 문제 ===== * 1708: 점은 100,000 개. 좌표의 범위는 40,000. * 100,000개 정도의 점에서 convex hull을 만드는 것은 300ms정도면 돌아간다. * 점 갯수가 좀더 많은 문제가 있어야지 성능 측정이 제대로 될거 같은데.. 그런 문제가 별로 없다. * 22962가 그나마 점은 500,000 개, 좌표의 범위는 10^9. 인데 얘는 볼록 다각형 내부의 점 판정이 추가로 필요해서 난이도가 좀더높다 ===== 확장 ===== ==== Decremental convex hull ==== ==== Nested convex hull ==== * [[https://codeforces.com/blog/entry/75929]] * [[https://judge.yosupo.jp/problem/convex_layers]] * [[https://stackoverflow.com/questions/9410184/sublinear-but-simple-dynamic-convex-hull-algorithm]] * [[https://en.wikipedia.org/wiki/Convex_layers]] ==== 원들의 볼록 껍질 ==== * 난이도 * O(nh) * O(nlogn) ==== 고차원으로 확장 ====