글 읽기 - 회전하는 캘리퍼스.. 어디가 잘못되었을까요? ㅠㅠ

wyldecat 5년 전 0

convex hull을 구한 뒤, leftmost와 rightmost 점에서 부터 시작하였습니다.

왼쪽에서 오른쪽으로 가는 점은 (0,-1)을 기준으로.. 오른쪽에서 왼쪽으로 가는 점은 (0, 1)을 기준으로,두 각도를 비교해주었는데요.

실수변환을 피하기 위해, 탄젠트값을 이용해서 비교를 해주었습니다.

딱히 문제될건 없는것 같은데 어디가 잘못되었을까요? ㅠㅠ

회전하는 캘리퍼스는 85번째 줄의 while문에 구현되어 있습니다.

#include <stdio.h>
#include <math.h>

#include <algorithm>
#include <vector>

#define MAXN 100000

int stk[MAXN];

long double dist(const std::pair<int, int> &a, const std::pair<int, int> &b)
{
    return sqrt(1.0 * pow(a.first - b.first, 2) +
        1.0 * pow(a.second - b.second, 2));
}

long long dist_square(const std::pair<int, int> &a,
    const std::pair<int, int> &b)
{
    return 1LL * (a.first - b.first) * (a.first - b.first) +
        1LL * (a.second - b.second) * (a.second - b.second);
}

long long ccw(const std::pair<int, int> &a, const std::pair<int, int> &b,
    const std::pair<int, int> &c)
{
    std::pair<int, int> A = { b.first - a.first, b.second - a.second };
    std::pair<int, int> B = { c.first - b.first, c.second - b.second };
    return 1LL * A.first * B.second - 1LL * A.second * B.first;
}

int main()
{
    std::vector<std::pair<int, int>> points;
    int N;

    scanf("%d", &N);
    for (int i = 0; i < N; i++) {
        int x, y;
        scanf("%d %d", &x, &y);
        points.push_back({ x, y });
    }

    std::sort(points.begin(), points.end());
    std::sort(points.begin() + 1, points.end(),
        [&](const std::pair<int, int> &a, const std::pair<int, int> &b) {
        long long _ccw = ccw(points[0], a, b);
        if (_ccw == 0) {
            return abs(a.first - points[0].first) + abs(a.second - points[0].second) <
                abs(b.first - points[0].first) + abs(b.second - points[0].second);
        }
        return _ccw > 0;
    });

    int top = 0;
    stk[top++] = 0;
    stk[top++] = 1;

    for (int i = 2; i < N; i++) {
        while (top > 1 && ccw(points[stk[top - 2]],
            points[stk[top - 1]], points[i]) <= 0) top--;
        stk[top++] = i;
    }

    long double ans = 0.0;
    std::pair<int, int> _lp, lp;
    std::pair<int, int> _rp, rp;
    int lx = 2e9, rx = -2e9;
    int li = 0, ri = 0, _li, _ri;

    for (int i = 0; i < top; i++) {
        if (lx > points[stk[i]].first) {
            lx = points[stk[i]].first;
            li = i;
        }
        if (rx < points[stk[i]].first) {
            rx = points[stk[i]].first;
            ri = i;
        }
    }

    _li = li;
    _ri = ri;

    while (_li != ri && _ri != li) {
        const std::pair<int, int> &left = points[stk[_li]];
        const std::pair<int, int> &right = points[stk[_ri]];
        const std::pair<int, int> &next_left = points[stk[(_li + 1) % top]];
        const std::pair<int, int> &next_right = points[stk[(_ri + 1) % top]];

        ans = std::max(ans, dist(left, right));

        if (_li == ri) {
            _ri = (_ri + 1) % top;
            continue;
        }
        else if (_ri == li) {
            _li = (_li + 1) % top;
            continue;
        }

        std::pair<int, int> diff_left = { left.second - next_left.second,
            next_left.first - left.first };
        std::pair<int, int> diff_right = { next_right.second - right.second,
            right.first - next_right.first };

        if (diff_left.first < 0 && diff_right.first >= 0) {
            _ri = (_ri + 1) % top;
        }
        if (diff_right.first < 0 && diff_left.first >= 0) {
            _li = (_li + 1) % top;
        }
        else if (diff_left.second * diff_right.first <
            diff_right.second * diff_left.first) {
            _li = (_li + 1) % top;
        }
        else if (diff_left.second * diff_right.first >
            diff_right.second * diff_left.first) {
            _ri = (_ri + 1) % top;
        }
        else {
            _li = (_li + 1) % top;
            _ri = (_ri + 1) % top;
        }
    }

    printf("%.10Lf\n", ans);
    return 0;
}

wyldecat 5년 전 0

하... while문안에 조건 두개를 ||로 연결해야 하는데.. &&로 해놨네요...

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

회전하는 캘리퍼스.. 어디가 잘못되었을까요? ㅠㅠ

wyldecat 5년 전 0

wyldecat 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말