Plane Sweeping - Right Hull Only
* 지금까지 본 점들의 Right Hull이 계산되어 있다고 믿는다.
새로 들어온 점은 더 오른쪽에 있기 떄문에 무조건 convex에 들어가게 될 것
중간의 점들이 사라지게 될 수 있다. 따라서 접선을 찾는다.
(기하문제에서는 점 3개가 일직선에 있지 않는다.
x좌표, y좌표가 다 다르다고 생각한다.)
right hull이 있고 오른쪽 점이 있다. (여태까지 본 x좌표 중 가장 큼)
접선을 구한다. (가장 모든 점을 쳐다봤을 때 가장 위쪽&가장 아래쪽이 접선이 된다,)
새로운 convex hull이 생긴다, (x표시가 빠짐)
더 밑에 점이 찍힌다면 위쪽 접선은 나오지만 밑은 다 사라지게 됨`
즉, 접선 2개를 구해야 한다.
전체 nlog n을 위해서 log n안에 접선 2개를 찾아야 한다.
뚫고 들어가는지, 다시 나오는지, 접선인지 알 수 있다.
-> convex위의 점들을 y좌표로 sorting해서 Balanced BST에 저장
-> 각 점은 양쪽 선분을 저장하고 있다.
1. special case : 위쪽이나 아래쪽 한군데만 생긴다
이 경우는 위쪽 접선은 없다.
2. special case 아닌경우:
2.1. convex hull안으로 뚫고 들어간다.(y좌표가 큰경우) => 위로가야함
왜냐하면 아래쪽 선분이 직선의 왼쪽에 있고 위쪽 선분이 오른쪽에 있으면 뚫고 들어가기 떄문
2.2. 뚫고 나간다. => 아래로 내려가야함
왼쪽이 높은점일 떄
2.3. 아래쪽 선분과 위쪽 선분이 둘다 왼쪽에 있음 => 접선
이런식으로 접선 찾음!
점 하나가 들어가고
사이의 점은 트리에서 빠진다.
위쪽 접선 찾는데에 O(log n)
아래쪽 접선 찾는데에 O(log n)
insert O(log n) -> 처음 등장했을 때 한 번 추가
delete O(k log n) -> 한번 제거될 수 있음
각 점은 한 번 추가되고 최대 한 번 제거된다.
총 시간 => n logn
tree를 써야 하기 떄문에 상수 오버헤드가 생겨 좋지는 않지만
일부분의 convex를 가지고 있다는 장점
Dynamic Case
n log n으로 계산했다고 가정
안쪽에 추가되는 점은 convex hull과 상관없다.
하지만 안쪽에 추가되었다는 사실을 어떻게 알 것인가?
=> BST
upper hull보다 아래쪽에 있는지 알아낸다.
똑바로 올라갔을 때 만나는 선분을 찾는다.
BST를 이용해서 내 위에 있는 선분을 알 수 있고,
CCW로 비교하면 위에 있는지 아래있는지 알 수 있다.
=> upper hull 아래쪽에 있고 lower hull 위쪽에 있으면 무시
upper hull위에 있다면 (밖에 있다면)
앞에 right hull처럼 접선 두개를 긋고 그 사이 점을 없애면 된다.
대망의 Divide and Conquer
upper hull (가장 왼쪽 점과 오른쪽 점을 무조건 들어가 있음)
아래쪽도 똑같이 있다고 생각해야 한다.
반 나눠서 왼쪽 upper hull과 오른쪽 upper hull이 계산되었다고 친다.
각각은 array에 저장했다고 생각 tree에 넣고 생각할 수 있지만 O(n)
=> 위쪽 공통 접선을 찾는다
중간은 버리고 공통접선을 긋고 해당되는 애들만 새로 array에 저장
왼쪽에서 아무곳에 점을 놓고 다른(오른쪽) 곳에 접선을 찾는다. (BST방법으로)
다른 곳(오른쪽)에서 반대쪽(왼쪽)을 다시 본다.
오른쪽 점 하나가 log n시간을 쓴다
왼쪽 점 하나도 log n시간을 쓴다. (log n개의 점을 왼쪽에 찍으며 찾는다.)
사는 것만 남겨서 upper hull을 새로 만드는 방법 nlog n
머지소트와 시간이 완전히 같다.
Farthest Point
제일 먼점 찾기(사이드 스토리-아이디어만 간략하게 설명)
convex hull을 구하고나면 제일 먼 점 찾기 가능~!
평행한 두 직선을 양쪽에서 밀어넣으면 부딪히는 점 2개!
=> 제일 먼 점의 쌍의 후보임
그리고 모든 각도에 대해서 평행한 두 직선을 다 해본다...
정말 전부는 아니고 사이의 각에 대해서!
'알고리즘' 카테고리의 다른 글
| 14-2 (0) | 2020.10.17 |
|---|---|
| 14 Dynamic Programming (0) | 2020.10.17 |
| 알고리즘12 Plane Sweeping (0) | 2020.10.13 |
| 알고리즘 11 (0) | 2020.10.07 |
| 알고리즘10 (0) | 2020.10.03 |
