[ Divide and Conquer ] Farthest Point
·
CS/Algorithm
가장 먼 점을 찾는 문제직관적으로 생각했을 때도, 가장 먼 점은 무조건 convex hull 위에 있어야한다. Rotating Calipers캘리퍼를 움직여서 가장 먼 것을 구하는 것이다. 왼쪽을 아무데서 구하고, 각도를 이용하여 "캘리퍼가 닿는 각도"를 확인한다. (180도가 넘는 각도)캘리퍼를 한바퀴 돌리면서 확인한다. 가장 먼 점의 쌍을 구하는 유일한 방법이다. Convex Hull을 구하면 풀 수 있으므로 O(NlogN)에 해결된다.