[BOJ/Platinum 3] 백준 9240 로버트 후드(C++)

문제 링크

https://www.acmicpc.net/problem/9240

9240번: 로버트 후드

 

문제

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

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

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

입력

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

출력

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

예제 입력 1

2
2 2
-1 -2

예제 출력 1

5.0

예제 입력 2

5
-4 1
-100 0
0 4
2 -3
2 300

예제 출력 2

316.86590223

알고리즘 분류

• 그레이엄 스캔
• 회전하는 캘리퍼스

풀이

두 개의 화살의 거리의 최댓값을 찾아야 한다. 화살 사이의 거리가 최대한 멀어야 하므로 가장자리에 있는 화살들만을 찾아야 한다.

기준점을 정하고 그레이엄 스캔을 통해 화살 집단의 테두리를 이루는 화살들만을 찾는다. 

그런데 화살의 개수가 너무 많으면, 단순히 이중반복문으로 비교한다면 시간 초과가 발생한다.

따라서 다른 방법을 찾아야 한다.

제일 먼저 X좌표가 가장 작은 점과 큰 점을 기준으로 한다. 그리고 두 점 사이의 거리를 구한다.

다음으로 각각의 점의 다음 점과의 벡터를 구하고 두 벡터를 외적 계산한다. 계산한 값이 0보다 작으면 왼쪽 벡터의 끝 점을 갱신해준다. 0보다 크면 오른쪽 벡터의 끝 점을 갱신해준다. 그리고 새로 갱신한 두 점 사이의 거리를 구해서 기존의 최댓값과 비교해 최댓값을 갱신한다.

이 방법으로 모든 가장자리의 화살들 사이의 거리를 탐색하여 더 작은 각도에 위치한 화살들을 찾으면서 거리의 최댓값을 구해준다.

참고)

[C++ 알고리즘] 회전하는 캘리퍼스 알고리즘 구현 (BOJ 8927번 : Squares)

코드

#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#define INF 2e9
#define LL long long
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
struct Point {
    LL X, Y;
};

int T;
LL N, X, Y, minX, maxY, First, Left, Right, CV_Count;
vector<Point> Vec;
vector<Point> CV;
int Answer;

void init() {
    minX = INF;
    maxY = -INF;
}

void input() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> X >> Y;
        Vec.push_back({X, Y});
    }
}

LL CCW(const Point &A, const Point &B, const Point &C) {
    LL OP = A.X * B.Y + B.X * C.Y + C.X * A.Y;
    OP -= (A.Y * B.X + B.Y * C.X + C.Y * A.X);
    return OP;
}

bool Comp(const Point &A, const Point &B) {
    LL ccwValue = CCW(Vec[0], A, B);
    if (ccwValue < 0) {
        return true;
    }
    else if (ccwValue > 0) {
        return false;
    }
    if (A.Y != B.Y) {
        return (A.Y > B.Y);
    }
    return (A.X < B.X);
}

void settings() {
    for (int i = 0; i < Vec.size(); i++) {
        if ((maxY < Vec[i].Y) || ((maxY == Vec[i].Y) && (minX > Vec[i].X))) {
            minX = Vec[i].X;
            maxY = Vec[i].Y;
            First = i;
        }
    }
    Vec[First].X = Vec[0].X;
    Vec[First].Y = Vec[0].Y;
    Vec[0].X = minX;
    Vec[0].Y = maxY;
    sort(Vec.begin() + 1, Vec.end(), Comp);
    for (int i = 0; i < Vec.size(); i++) {
        while ((CV.size() >= 2) && (CCW(CV[CV.size() - 2], CV.back(), Vec[i]) >= 0)) {
            CV.pop_back();
        };
        CV.push_back(Vec[i]);
    }
    CV_Count = CV.size();
    for (int i = 0; i < CV_Count; i++) {
        if (CV[i].X < CV[Left].X) {
            Left = i;
        }
        if (CV[i].X > CV[Right].X) {
            Right = i;
        }
    }
    Answer = (CV[Left].X - CV[Right].X) * (CV[Left].X - CV[Right].X) + (CV[Left].Y - CV[Right].Y) * (CV[Left].Y - CV[Right].Y);
    Point Center;
    Center.X = 0;
    Center.Y = 0;
    for (int i = 0; i < CV_Count; i++) {
        Point Prev;
        Prev.X = CV[(Left + 1) % CV_Count].X - CV[Left].X;
        Prev.Y = CV[(Left + 1) % CV_Count].Y - CV[Left].Y;
        Point Next;
        Next.X = CV[Right].X - CV[(Right + 1) % CV_Count].X;
        Next.Y = CV[Right].Y - CV[(Right + 1) % CV_Count].Y;
        if (CCW(Center, Prev, Next) < 0) {
            Left = (Left + 1) % CV_Count;
        }
        else {
            Right = (Right + 1) % CV_Count;
        }
        int Value = (CV[Left].X - CV[Right].X) * (CV[Left].X - CV[Right].X) + (CV[Left].Y - CV[Right].Y) * (CV[Left].Y - CV[Right].Y);
        Answer = max(Answer, Value);
    }
}

void find_Answer() {
    cout << fixed;
    cout.precision(8);
    cout << sqrt(Answer) << "\n";
}

int main() {
    FASTIO
    init();
    input();
    settings();
    find_Answer();

    return 0;
}