hellogaon

회전하는 캘리퍼스 알고리즘(Rotating Calipers Algorithm)은 캘리퍼스로 무언가를 재는 과정을 알고리즘화 한 것 입니다.캘리퍼스는 작은 물건의 지름, 너비등을 측정할 때 쓰는 도구로 두 개의 평행한 변 사이에 물체를 끼우고 변 사이를 측정합니다.기하 문제에서는 이를 볼록 다각형에 완전히 포함하는 가장 긴 선분의 길이를 구하는 용도로 쓸 수 있습니다.이 때 이 길이를 볼록 다각형의 지름이라고도 합니다.회전하는 캘리퍼스 알고리즘은 실제 캘리퍼스와 비슷하게 다각형을 평행한 두 직선 사이에 끼우고다각형을 따라 두 직선을 한 바퀴 돌리면서 두 직선에 닿는 꼭지점들 간의 거리를 구합니다.이를 좀 더 편하게 구현하기 위하여 가장 왼쪽에 있는 점과 오른쪽에 있는 점에 수직선을 붙이고 시작한 뒤,어느 ..