[ Divide and Conquer ] Farthest Point

가장 먼 점을 찾는 문제

직관적으로 생각했을 때도, 가장 먼 점은 무조건 convex hull 위에 있어야한다. 

Rotating Calipers

캘리퍼를 움직여서 가장 먼 것을 구하는 것이다. 

왼쪽을 아무데서 구하고, 각도를 이용하여 "캘리퍼가 닿는 각도"를 확인한다. (180도가 넘는 각도)

캘리퍼를 한바퀴 돌리면서 확인한다. 

 

 

가장 먼 점의 쌍을 구하는 유일한 방법이다.

 

Convex Hull을 구하면 풀 수 있으므로 O(NlogN)에 해결된다.