백준 9240번 : 로버트 후드 (C++)

접근

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

9240번: 로버트 후드

백준 1708번 볼록 껍질 문제를 풀 때 쓰였던 convex hull 알고리즘을 이용하고, 구해진 볼록 다각형의 각 꼭짓점을 돌면서 최대 거리를 갱신하면서 탐색하면 풀 수 있는 문제였다.

https://ca.ramel.be/245

백준 1708번 : 볼록 껍질 (C++)

convex hull 알고리즘을 통해 최외각 점들을 모두 체크한 후, 이 점들 사이의 거리를 갱신하는 과정에 brute force 방법을 통해 모두 체크해줘도 풀 수 있고, 로테이팅 캘리퍼스(rotating callipers) 라는 알고리즘을 이용하면 시간을 좀 더 단축할 수 있다.

로테이팅 캘리퍼스란 말그대로 회전하는 캘리퍼스라는 뜻으로, 캘리퍼스로 측정하는 것과 같이 convex hull 로 구해진 다각형의 최외각을 한바퀴 탐색하며 최대거리를 갱신해주게 된다. 자세한 설명은 아래 링크를 참고하자.

https://stonejjun.tistory.com/42

Geometry (4) - 로테이팅 캘리퍼스

코드

#include <math.h>

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

#define endl '\n'
#define MAX_N 100001

struct ARROW {
    int x;
    int y;
};
ARROW operator-(ARROW a, ARROW b) {
    ARROW c;
    c.x = a.x - b.x;
    c.y = a.y - b.y;
    return c;
}

int N;
vector<ARROW> Arrow;
vector<ARROW> s;

long long ccw(ARROW a, ARROW b, ARROW c) {
    long long res = (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
    return res;
}

bool cmp(ARROW a, ARROW b) {
    if (a.y == b.y) {
        return a.x < b.x;
    } else {
        return a.y < b.y;
    }
}

bool cmpccw(ARROW a, ARROW b) {
    long long val = ccw(Arrow[0], a, b);
    if (val) {
        return val > 0;
    } else if (a.y == b.y) {
        return a.x < b.x;
    } else {
        return (a.y < b.y);
    }
}

int dist(ARROW a, ARROW b) {
    int res = (b.x - a.x) * (b.x - a.x) + (b.y - a.y) * (b.y - a.y);
    return res;
}

int main(int argc, char** argv) {
    // freopen 주석 처리
    freopen("input.txt", "r", stdin);

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cout << fixed;
    cout.precision(8);

    cin >> N;
    int a, b;
    for (int i = 0; i < N; i++) {
        cin >> a >> b;
        Arrow.push_back({a, b});
    }
    if (N == 2) {
        cout << sqrt(dist(Arrow[0], Arrow[1])) << endl;
        return 0;
    }
    sort(Arrow.begin(), Arrow.end(), cmp);
    sort(Arrow.begin() + 1, Arrow.end(), cmpccw);
    ARROW tmp1, tmp2;
    for (int i = 0; i < N; i++) {
        while (s.size() >= 2) {
            tmp2 = s.back();
            s.pop_back();
            tmp1 = s.back();
            if (ccw(tmp1, tmp2, Arrow[i]) > 0) {
                s.push_back(tmp2);
                break;
            }
        }
        s.push_back(Arrow[i]);
    }
    int Size = s.size();

    // Brute Force 문제 풀이

    // int ans = 0;
    // for (int i = 0; i < Size - 1; i++) {
    //     for (int j = i + 1; j < Size; j++) {
    //         ans = max(ans, dist(s[i], s[j]));
    //     }
    // }
    // cout << sqrt(ans) << endl;

    // Rotating Callipers 문제 풀이

    int lp = 0, rp = 0;
    for (int i = 0; i < Size; i++) {
        if (s[i].x < s[lp].x) lp = i;
        if (s[i].x > s[rp].x) rp = i;
    }
    int ans = dist(s[lp], s[rp]);
    ARROW Origin = {0, 0};
    for (int i = 0; i < Size; i++) {
        if (ccw(Origin, s[(lp + 1) % Size] - s[lp], s[(rp + 1) % Size] - s[rp]) < 0) {
            lp = (lp + 1) % Size;
        } else {
            rp = (rp + 1) % Size;
        }
        ans = max(ans, dist(s[lp], s[rp]));
    }
    cout << sqrt(ans) << endl;

    return 0;
}

더 생각해 볼 것?

...

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!