Rotating Calipers

0. 개요 Rotating Calipers 또는 회전하는 캘리퍼스 라고 부른다. 2차원 좌표평면에 점들이 주어졌을 때, 가장 먼 두 점과 그 거리를 찾는 알고리즘이다. 알고리즘의 동작 방식이 마치 캘리퍼스를 사용하는 것 같아서 붙은 이름인 듯 하다. 1. 가장 먼 두 점 찾기 그림과 같이 2차원 좌표평면에 수많은 점들이 있다. 이 중 가장 먼 두 점을 찾고 싶을 때, 어떻게 하면 좋을까? 1) 모든 점 사이의 거리 계산하기 가장 먼저 떠오르는 방법은 무식하게(?) 모든 쌍을 찾아서 길이를 비교하는 것이다. 점이 $N$개라면 시간 복잡도가 $O(N^2)$ 이 나올 것이 뻔하다. 우리는 조금 더 빠른 시간 안에 해결할 알고리즘을 찾기 때문에, 생각을 전환해보자. 가장 먼 두 점이 될 수 있는 후보는 어떤 점..

Convex Hull

0. 개요 2차원 좌표평면에 점들이 주어졌을 때, 모든 점을 포함하는 볼록다각형 중 가장 면적이 작은 것을 만드는 알고리즘이다. 1. Convex Hull Convex Hull 은 볼록 껍질이라고도 부른다. 주어진 점들을 모두 포함하는 가장 작은 볼록다각형인데, 최외곽에 있는 점들의 일부로 구성된다는 특징이 있다. (당연하다) Convex Hull 은 점들의 회전 방향인 CCW 를 이용해서 만들 수 있다. 2. CCW Convex Hull 알고리즘을 알아보기 전에 CCW 를 간단히 코드로 복습해보자. 점 base → A → B 로 이어지는 회전 방향이 시계 반대 방향이면 양수, 시계 방향이면 음수, 일직선이면 0 을 리턴한다. typedef long long ll; struct Point { int x,..