[백준] 9240 - 로버트 후드 (java)

HaYeong Jang·2021년 1월 19일

ccw convex-hull geometry rotating calipers 백준 알고리즘

[백준] 알고리즘

목록 보기

11/62

문제

로버트 후드는 로빈 후드의 동생이다. 로버트 후드는 자신의 형처럼 전설적인 인물이 되기 위해 활 쏘기를 연습하고 있다.

이번에 노팅엄에서 열린 활 쏘기 대회는 현대에 열리는 양궁과 규칙이 다르다. 양궁은 더 많은 점수를 쏜 사람이 승리하는 방식이다. 하지만, 노팅엄 활 쏘기 대회에서는 과녁에 맞은 화살 사이의 거리 중 최댓값이 가장 큰 사람이 승리한다.

로버트 후드는 총 C발을 발사했고, 모든 화살은 과녁에 적중했다. 과녁을 이차원 평면으로, 화살은 점으로 나타낸다. 화살의 좌표가 주어졌을 때, 가장 먼 화살의 거리를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 로버트 후드가 발사한 화살의 수 C (2 ≤ C ≤ 100,000)가 주어진다. 다음 C개 줄에는 화살의 좌표가 주어진다. 좌표는 정수이고, 절댓값은 1,000을 넘지 않는다.

출력

가장 먼 두 화살의 거리를 출력한다. 상대/절대 오차가 10-6 이내인 경우에만 정답이다.

예제 입력

예제 출력

316.86590223

코드

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

class Point {
    long x, y;

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

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

        int C = Integer.parseInt(st.nextToken());
        ArrayList<Point> points = new ArrayList<>();

        for (int i = 0; i < C; i++) {
            st = new StringTokenizer(br.readLine());
            long x = Long.parseLong(st.nextToken());
            long y = Long.parseLong(st.nextToken());

            points.add(new Point(x, y));
        }

        ArrayList<Point> list = new ArrayList<>(convexHull(points));
        bw.write(rotatingCalipers(list) + "\n");

        br.close();
        bw.flush();
        bw.close();
    }

    static double rotatingCalipers(ArrayList<Point> convexHull) {
        double max_dist = 0;
        int j = 1;
        for (int i = 0; i < convexHull.size(); i++) {
            int i_next = (i + 1) % convexHull.size();
            for (; ; ) {
                int j_next = (j + 1) % convexHull.size();

                long bx = convexHull.get(i_next).x - convexHull.get(i).x; // 왼쪽 벡터
                long by = convexHull.get(i_next).y - convexHull.get(i).y;
                long cx = convexHull.get(j_next).x - convexHull.get(j).x;   // 오른쪽 벡터
                long cy = convexHull.get(j_next).y - convexHull.get(j).y;

                long ccw = ccw(new Point(0, 0), new Point(bx, by), new Point(cx, cy));
                if (ccw > 0) {  // 반시계 방향이면 오른쪽에 있는 점을 다음으로
                    j = j_next;
                } else {    // 시계 방향이면 왼족에 있는 점을 다음으로
                    break;
                }
            }

            // 최대 거리 구하기
            if (dist(convexHull.get(i), convexHull.get(j)) > max_dist) {
                max_dist = dist(convexHull.get(i), convexHull.get(j));
            }
        }
        return max_dist;
    }

    static Point root = new Point(Long.MAX_VALUE, Long.MAX_VALUE);

    static Stack<Point> convexHull(ArrayList<Point> input) {
        // 기준점 찾기
        for (int i = 0; i < input.size(); i++) {
            if (input.get(i).x < root.x) {
                root = input.get(i);
            } else if (input.get(i).x == root.x) {
                if (input.get(i).y < root.y) {
                    root = input.get(i);
                }
            }
        }

        // 모든 점들을 반시계 방향으로 정렬하기
        input.sort(new Comparator<Point>() {
            @Override
            public int compare(Point o1, Point o2) {
                long ccw = ccw(root, o1, o2);

                if (ccw > 0) {
                    return -1;
                } else if (ccw < 0) {
                    return 1;
                } else {
                    double distance1 = dist(root, o1);
                    double distance2 = dist(root, o2);

                    return Double.compare(distance1, distance2);
                }
            }
        });

        Stack<Point> stack = new Stack<>();
        stack.add(root);

        for (int i = 1; i < input.size(); i++) {
            while (stack.size() > 1 && (ccw(stack.get(stack.size() - 2), stack.get(stack.size() - 1), input.get(i)) <= 0)) {
                stack.pop();
            }
            stack.add(input.get(i));
        }

        return stack;
    }

    static long ccw(Point p1, Point p2, Point p3) {
        return (p1.x * p2.y + p2.x * p3.y + p3.x * p1.y) - (p1.y * p2.x + p2.y * p3.x + p3.y * p1.x);
    }

    static double dist(Point p1, Point p2) {
        return Math.sqrt((p2.x - p1.x) * (p2.x - p1.x) + (p2.y - p1.y) * (p2.y - p1.y));
    }
}

정리

알고리즘
1. x가 가장 작은 값을 기준으로 하여 Convex Hull을 구한다.
2. i와 i_next(왼쪽), j와 j_next(오른쪽)가 이루는 각도를 비교한다.
3. CCW면 j를 j_next로 옮긴다.
4. CW면 옮기지 않고 for문을 빠져 나온다.
5. 두 점 사이의 거리를 구한다.
6. i를 i_next로 옮긴다.

처음에 Comparator의 compare 메소드를 꼼꼼히 정의하지 않아서 런타임 에러(IllegalArgument)가 나왔다. compare 메소드를 재정의할 때 주의해야겠다.