가장 먼 두 점 (회전하는 캘리퍼스)

주어진 점들 중에 가장 먼 두 점을 구하는 문제는 Convex Hull을 이용해 해결할 수 있다.
Convex Hull은 모든 점을 둘러싸는 외곽의 점들로만 이루어져 있으므로, 가장 먼 두 점은 반드시 Convex Hull을 이루는 점 중에 존재할 수밖에 없다.

보통 회전하는 캘리퍼스 방법이라고 부르는 듯 한데, 캘리퍼스는 길이를 재는 도구이다.
마치 Convex Hull에 그 도구를 사용하듯이, Convex Hull의 두 점 사이의 길이를 재면서 문제를 푸는 방법이다.

코드는 아래와 같다.

#define MAXN 10000		// 점의 개수

typedef long long ll;

/********** 자료구조 구현 *********/

struct Point {
	int x;
    int y;
    
    // 연산자 오버로딩
    Point operator-(Point other) {
    	Point ret;
        ret.x = this->x - other.x;
        ret.y = this->y - other.y;
        
        return ret;
    }
};

// 배열로 스택 구현
struct Stack {
	Point data[MAXN];
    int stackTop;
    
    void init() { stackTop = 0; }
    
    int getSize() { return stackTop; }
    
    bool isEmpty() { return stackTop == 0; }
    
    void push(Point newData) { data[stackTop++] = newData; }
    
    Point pop() { return data[--stackTop]; }
    
    Point top() { return data[stackTop - 1]; }
    
    Point* getDataList() { return data; }
};

/********** 전역변수 선언 *********/

Point points[MAXN];		// Point가 담겨있는 배열 -> arr
Point temp[MAXN];		// merge sort를 위한 임시 배열
Stack stack;

Point base;				// 시계 반대 방향 정렬 시 사용될 기준

/********** Util 함수 구현 *********/

ll ccw(Point a, Point b) {
	return a.x * b.y - a.y * b.x;
}

ll ccw(Point base, Point a, Point b) {
	return ccw(a - base, b - base);
}

// base -> a -> b 가 시계 반대 방향인지 확인하는 함수
bool isTurnLeft(Point base, Point a, Point b) {
	return ccw(base, a, b) > 0;
}

// 점 a와 점 b 사이의 거리 (제곱근 X)
ll getDistance(Point a, Point b) {
	ll diffX = a.x - b.x;
    ll diffY = a.y - b.y;
    
    return diffX * diffX + diffY * diffY;
}

// y좌표가 작은 순으로, 같다면 x 좌표가 작은 순으로 정렬
// 앞의 점의 우선순위가 높다면 true
bool cmpYX(Point a, Point b) {
	int cmp = a.y - b.y;
    if(cmp == 0) cmp = a.x - b.x;
    
    return cmp < 0;
}

// base를 기준으로, 시계 반대 방향으로 정렬
// 앞의 점이 더 각도가 작다면 true
bool cmpCCW(Point a, Point b) {
	ll res = ccw(base, a, b);
    // 일직선이라면, base에 더 가까운 점이 우선
    if(res == 0) return getDistance(base, a) < getDistance(base, b);
    
    return res > 0;
}

// 주어진 배열을 주어진 compare 함수에 따라 merge sort
void mergeSort(Point arr[], int start, int end, bool (*compare)(Point, Point)) {
	if(start >= end) return;
    
    // Divide
    int mid = (start + end) >> 1;
    mergeSort(arr, start, mid, compare);
    mergeSort(arr, mid+1, end, compare);
    
    // Merge
    int left = start;
    int right = mid + 1;
    int idx = start;
    while(left <= mid && right <= end) {
    	temp[idx++] = compare(arr[left], arr[right]) ?
        			  arr[left++] : arr[right++];
    }
    
    // 왼쪽 배열이 남은 경우
    while(left <= mid) temp[idx++] = arr[left++];
    
    // 오른쪽 배열이 남은 경우
    while(right <= end) temp[idx++] = arr[right++];
    
    // temp에서 arr로 원상복구
    for(int i=start; i<=end; i++) arr[i] = temp[i];
}

/********** 회전하는 캘리퍼스 구현 *********/

// *convexHull: Convex Hull을 이루는 점들이 담긴 배열
// size: Convex Hull을 이루는 점들의 개수
void getMaxDist(Point *convexHull, int size) {
	// 1. 맨 앞의 두 점으로 가장 먼 두 점의 인덱스 초기화
    int p1 = 0, p2 = 1;
    int maxDist = getDistance(convexHull[p1], convexHull[p2]);
    
    // 2. 회전하면서 확인 -> size의 2배만큼 반복
    for(int i=0; i<size*2; i++) {
    	int np1 = (p1 + 1) % size;	// p1의 다음 점
        int np2 = (p2 + 1) % size;	// p2의 다음 점
        
        int res = ccw(convexHull[np1] - convexHull[p1],
        			  convexHull[np2] - convexHull[p2]);
                      
        if(res < 0) p1 = np1;
        else if(res > 0) p2 = np2;
        else { p1 = np1; p2 = np2; }
        
        int dist = getDistance(convexHull[p1], convexHull[p2]);
        if(maxDist < dist) maxDist = dist;
    }
    
    // 3. 이 시점에서 p1과 p2에는 convexHull에서 가장 먼 두 점의 인덱스가 담겨 있다.
    // maxDist는 가장 먼 거리가 담겨있다.
}

/********** Convex Hull 구현 *********/

// arr[]: 점들이 담겨있는 배열
// N: 점의 전체 개수
void getConvexHull(Point arr[], int N) {
	// 1. 좌표 순으로 정렬
    mergeSort(arr, 0, N-1, cmpYX);
    
    // 2. base 기준으로 시계 반대 방향 정렬
    base = arr[0];
    mergeSort(arr, 1, N-1, cmpCCW);
    
    // 3. Stack 초기화 -> 기본으로 점 2개 넣고 시작
    stack.init();
    stack.push(arr[0]);
    stack.push(arr[1]);
    
    // 4. Convex Hull 찾기 -> 모든 점을 한 번씩 확인
    for(int i=2; i<N; i++) {
    	while(stack.getSize() >= 2) {
        	Point first = stack.pop();		// 직전 점
            Point base = stack.top();		// 2개 전의 점 (기준 점)
            
            // base -> first -> arr[i] 가 시계 반대 방향인지 확인
            if(isTurnLeft(base, first, arr[i]) {
            	stack.push(first);		// 뺐으니까 원상복구
                break;
            }
        }
        // stack에 현재 점 추가
        stack.push(arr[i]);
    }
    
    // 이 시점에서 stack에는 Convex Hull을 이루는 점들만 들어있다.
    
    // 5. 회전하는 캘리퍼스
    getMaxDist(stack.getDataList(), stack.getSize());
}