가장 거리가 먼 두 점 - FARTHEST_PAIR

문제 링크(koitp.org/problem/FARTHEST_PAIR/)

답이 되는 두 점의 쌍은 컨벡스헐 위에 존재한다.

컨벡스헐 위의 점들에 대해서 로테이팅 캘리퍼스로 답을 탐색한다.

로테이팅 캘리퍼스에서 판단 기준은 유클리드 거리가 아닌 CCW로 판단한다.

구간의 양 끝이 [A, B]라고 한다면,

A번째 점과 A+1번째 점을 잇는 선분과, B번째 점과 B+1번째 점을 잇는 선분의 외적을 계산해 방향이

왼쪽으로 계속 꺽이다가 오른쪽으로 꺽이게 되는 순간 멈추면 된다.