회전하는 캘리퍼스

회전하는 캘리퍼스 알고리즘(Rotating Calipers Algorithm)은 캘리퍼스로 무언가를 재는 과정을 알고리즘화 한 것 입니다.

캘리퍼스는 작은 물건의 지름, 너비등을 측정할 때 쓰는 도구로 두 개의 평행한 변 사이에 물체를 끼우고 변 사이를 측정합니다.

기하 문제에서는 이를 볼록 다각형에 완전히 포함하는 가장 긴 선분의 길이를 구하는 용도로 쓸 수 있습니다.

이 때 이 길이를 볼록 다각형의 지름이라고도 합니다.

회전하는 캘리퍼스 알고리즘은 실제 캘리퍼스와 비슷하게 다각형을 평행한 두 직선 사이에 끼우고

다각형을 따라 두 직선을 한 바퀴 돌리면서 두 직선에 닿는 꼭지점들 간의 거리를 구합니다.

이를 좀 더 편하게 구현하기 위하여 가장 왼쪽에 있는 점과 오른쪽에 있는 점에 수직선을 붙이고 시작한 뒤,

어느 직선이 먼저 다각형의 다른 점을 만나는 지 각도를 계산하여 두 각도 중 더 작은 쪽으로 두 직선을 회전하는 과정을

반 바퀴를 돌아서 두 직선이 서로 위치를 바꿀 때까지 반복하여 구하게 됩니다.

이 알고리즘을 응용하여 점들의 가장 먼 두 점 사이의 거리를 구할 때

점들의 볼록껍질을 구한 뒤 이 볼록껍질의 지름을 구하여 값을 알아낼 수도 있습니다.

기본 문제

10254번: 고속도로