테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.
====== 볼록 껍질 (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)

==== 고차원으로 확장 ====