[붕어빵 꼬리먼저 팀] 4회차 - 학습 마무리

2021/01/21 동계 모각코 4회차

오늘 공부하고자 했던 회전하는 캘리퍼스에 대한 이해와 문제 풀이를 마쳤습니다.

---

[회전하는 캘리퍼스] www.acmicpc.net/problem/10254

회전하는 캘리퍼스를 사용하여 가장 먼 두 점을 구하는 문제입니다.

 

우선 존재하는 모든 점들에서 가장 먼 두 점을 찾기 위해서는 볼록껍질을 사용합니다.

주어진 점 중에 가장 먼 두점이 볼록껍질 위에 존재함은 직관적으로 떠올릴 수 있습니다.

 

그러나 볼록껍질을 구한 후에 볼록껍질에 해당되는 모든 점들에 대해서 가장 먼 거리를 찾는 것도 $O(N^2)$입니다.

N의 크기가 줄었을 뿐, 시간복잡도 면에서는 여전히 부족합니다.

 

이런 문제를 해결하기 위해 회전하는 캘리퍼스라는 알고리즘을 사용하는데, $O(N)$에 볼록껍질에서 가장 먼 거리 및 두 점을 구할 수 있게됩니다.

두 포인터 기반의 이 알고리즘은 볼록껍질에 존재하는 두 점을 잡고 특정 방향으로 나아갈 때, 해당 점에서 그은 평행선들과의 각도를 확인하여 각도가 작은 쪽부터 다음으로 이동하여 다시 거리를 측정하는 방식으로 최장거리를 확인합니다.

필요 없는 점들을 굳이 확인하지 않아서 시간 복잡도를 줄이는 케이스입니다.

 

문제는 설명으로만 들어도 어려운 구현을 직접 짜는 것은 더 어렵습니다.

평행선을 만들고 각도를 확인하고 다음으로 이동하고 등등의 복잡한 과정을 거치면, 실수 오차 범위에 인해 틀리게 됩니다.

 

실수 연산이 오차가 크고, 복잡하여 이 때 다시 사용하는 것이 벡터의 외적, 즉 ccw입니다.

ccw가 세 점에 대해서 외적을 확인했다면 두 반직선을 사용해서도 외적을 확인할 수 있고, 이를 이용하여 현재 진행 중 인 두 점이 다음으로 가는 반직선을 사용하여 한 점의 도착점과 다른 점의 출발점을 잇고 ccw를 구하여 그 결과에 따라 점의 진행을 체크한다면 실수 오차를 피할 수 있습니다.

구체적인 값을 필요로 하지 않고 두 벡터가 평행선과 이루는 각도의 대소만 비교하면 되므로 위와 같이 정수로만 연산하는 벡터의 외적으로도 해결이 가능하게 된 것입니다.

 

그렇게 출발점이 원위치로 돌아오거나, 180도만 회전해도 최장 거리를 구할 수 있습니다.

 

원래 컨벡스 헐을 구현할 때 Graham Scan 알고리즘으로 구현하였으나 회전하는 캘리퍼스를 구현하는 것이 상당히 어려워 보여서 Monotone Chain 알고리즘을 사용하였습니다.

Graham Scan이 일반적인 볼록 껍질을 구현하는 것이라면, Monotone Chain은 위 볼록 껍질과 아래 볼록껍질을 따로 구현합니다.

하나의 껍질에서 따로 두 점을 분리해서 캘리퍼스를 돌리는 작업보다 두 껍질에서 돌리는 것이 더 간단하게 구할 수 있습니다.

 

 

[소스 코드] / Java

 

import java.io.*;
import java.util.*;

public class Main {
    private static Point[] dots;
    private static Deque<Point> up, down;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        int T = Integer.parseInt(br.readLine());
        while (T-- > 0) {
            int N = Integer.parseInt(br.readLine().trim());
            dots = new Point[N];

            for (int i = 0; i < N; i++) {
                st = new StringTokenizer(br.readLine(), " ");
                int x = Integer.parseInt(st.nextToken()), y = Integer.parseInt(st.nextToken());
                dots[i] = new Point(x, y);
            }

            monotoneChain(N);
            bw.write(getFarthestPair());
        }
        
        bw.flush();
        bw.close();
        br.close();
    }

    private static String getFarthestPair() {
        StringBuilder sb = new StringBuilder();
        long dis = -1;
        Point first = null, second = null;

        while (up.size() != 1 || down.size() != 1) {
            Point A = down.removeLast(), C = up.removeFirst();
            long newdis = getDistance(A, C);

            if (dis < newdis) {
                first = A; second = C;
                dis = newdis;
            }

            if (up.isEmpty()) {
                up.add(C);
            } else if (down.isEmpty()) {
                down.add(A);
            } else {
                Point B = down.peekLast(), D = up.peekFirst();
                if (CCW(A, B, C, D) < 0) {
                    up.offerFirst(C);
                } else {
                    down.offerLast(A);
                }
            }
        }

        sb.append(first.x).append(' ').append(first.y).append(' ').append(second.x).append(' ').append(second.y).append('\n');
        return sb.toString();
    }

    private static void monotoneChain(int N) {
        Arrays.sort(dots);

        up = new ArrayDeque<>(); down = new ArrayDeque<>();
        up.push(dots[0]); down.push(dots[0]);

        for (int i = 1; i < N; i++) {
            Point cur = dots[i];

            while (up.size() > 1) {
                Point pre = up.pop(), top = up.peek();
                if (CCW(top, pre, cur) < 0) {
                    up.push(pre);
                    break;
                }
            }
            up.push(cur);
            
            while (down.size() > 1) {
                Point pre = down.pop(), top = down.peek();
                if (CCW(top, pre, cur) > 0) {
                    down.push(pre);
                    break;
                }
            }
            down.push(cur);
        }
    }

    private static long getDistance(Point p1, Point p2) {
        return Pow(p2.x - p1.x) + Pow(p2.y - p1.y);
    }

    // 두 반직선
    private static int CCW(Point A, Point B, Point C, Point D) {
        Point newD = new Point(D.x + B.x - C.x, D.y + B.y - C.y);
        return CCW(A, B, newD);
    }

    // 세 점
    private static int CCW(Point p1, Point p2, Point p3) {
        long S = (long) p1.x * p2.y + (long) p2.x * p3.y + (long) p3.x * p1.y;
        S -= (long) p1.y * p2.x + (long) p2.y * p3.x + (long) p3.y * p1.x;
        if (S == 0) return 0;
        return S < 0 ? -1 : 1;
    }

    private static long Pow(int n) {
        return (long) n * n;
    }

    private static class Point implements Comparable<Point> {
        int x, y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }

        public int compareTo(Point p) {
            if (this.x == p.x) {
                return this.y < p.y ? -1 : 1;
            }
            return this.x < p.x ? -1 : 1;
        }
    }
}