[C++ 백준 풀이] 1310번 : 달리기 코스 / 10254번 : 고속도로 (Rotating Calipers)

이 포스트는 프로그래밍 문제 사이트 백준 Online Judge의 1310번 : '달리기 코스', 10254번 : '고속도로' 문제의 풀이 코드와 해설을 다루고 있습니다.

 

문제의 난이도는 Solved.ac 기준 Platinum II에 해당하며, 문제를 풀이하기 위해 회전하는 캘리퍼스(Rotating Calipers) 알고리즘에 대해 알고 있어야 합니다.

 

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

↑ 회전하는 캘리퍼스 알고리즘에 대한 구현과 설명은 위의 링크에 정리되어 있으니 참고해주시면 좋습니다.

 

그럼 바로 문제를 풀이해보도록 하겠습니다.

 

 

1310번 : 달리기 코스

1310번: 달리기 코스

 

필요한 부분만 첨부하여 문제를 요약하자면, 주어진 N개 기둥의 좌표에 대해 가장 거리가 먼 두 기둥 사이의 거리의 제곱을 구하는 문제입니다.

당연히 모든 기둥의 쌍에 대해 거리를 조사하게 되면 O(N^2) 알고리즘이 되므로 시간 초과를 발생시키게 됩니다.

따라서 Convex Hull 알고리즘을 이용해 볼록다각형을 구성하는 꼭짓점들을 선택한 뒤, 이 꼭짓점들을 대상으로 Rotating Calipers 알고리즘을 사용하여 거리가 가장 먼 두 점 사이의 거리를 구할 수 있습니다.

 

↓ 풀이 코드는 아래 접은 글에 정리되어 있습니다.

#include <cstdio>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;

struct Coor { long long x, y; };
Coor operator-(Coor a, Coor b) {
    Coor c;
    c.x = a.x - b.x;
    c.y = a.y - b.y;
    return c;
}
vector<Coor> Point;

long long CCW(Coor a, Coor b, Coor c) { return a.x*(b.y-c.y) + b.x*(c.y-a.y) + c.x*(a.y-b.y); }
long long DistSq(Coor a, Coor b) { return (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y); }

bool minCCW(Coor a, Coor b) {
    long long Value = CCW(Point[0], a, b);
    if(Value != 0) return Value > 0;
    else if(a.y != b.y) return a.y < b.y;
    else return a.x < b.x;
}

int main() {
    int N;
    scanf("%d", &N);
    Point.resize(N);
    for(int i=0; i<N; i++) scanf("%lld %lld", &Point[i].x, &Point[i].y);
    for(int i=1; i<N; i++) {
        if(Point[i].y < Point[0].y || (Point[i].y == Point[0].y && Point[i].x < Point[0].x)) {
            long long temp = Point[0].x;
            Point[0].x = Point[i].x;
            Point[i].x = temp;
            temp = Point[0].y;
            Point[0].y = Point[i].y;
            Point[i].y = temp;
        }
    }
    sort(Point.begin()+1, Point.end(), minCCW);

    stack<Coor> Convex;
    Coor Temp1, Temp2;
    Convex.push(Point[0]);
    Convex.push(Point[1]);
    for(int i=2; i<N; i++) {
        while(Convex.size() >= 2) {
            Temp2 = Convex.top();
            Convex.pop();
            Temp1 = Convex.top();
            if(CCW(Temp1, Temp2, Point[i]) > 0) {
                Convex.push(Temp2);
                break;
            }
        }
        Convex.push(Point[i]);
    }
    vector<Coor> Vertex;
    int Size = Convex.size();
    Vertex.resize(Size);
    for(int i=Size-1; i>=0; i--) {
        Vertex[i] = Convex.top();
        Convex.pop();
    }

    int LPoint = 0, RPoint = 0;
    for(int i=0; i<Size; i++) {
        if(Vertex[i].x < Vertex[LPoint].x) LPoint = i;
        if(Vertex[i].x > Vertex[RPoint].x) RPoint = i;
    }
    long long DiaSq = DistSq(Vertex[LPoint], Vertex[RPoint]);
    Coor Origin; Origin.x = 0, Origin.y = 0;
    for(int i=0; i<Size; i++) {
        if(CCW(Origin, Vertex[(LPoint+1)%Size]-Vertex[LPoint], Vertex[RPoint]-Vertex[(RPoint+1)%Size]) > 0)
            LPoint = (LPoint + 1)%Size;
        else RPoint = (RPoint + 1)%Size;
        if(DistSq(Vertex[LPoint], Vertex[RPoint]) > DiaSq)
            DiaSq = DistSq(Vertex[LPoint], Vertex[RPoint]);
    }
    printf("%lld", DiaSq);
}

 

 

구현 자체는 일반적인 Rotating Calipers 문제와 똑같기 때문에, 그대로 구현해주면 되지만 입력 범위가 좌표의 절댓값이 5만 이하이므로, 극단적으로 보았을 때 (50000, 50000)과 (-50000, -50000)이 입력되면 이 경우 거리의 제곱이 int 범위를 넘게 됩니다.

따라서 모든 변수의 자료형을 long long으로 설정한 뒤 풀이해야 오버플로우가 발생하지 않아 WA를 피할 수 있습니다.

 

 

 

풀이를 제출하면 40ms 시간이 소요되고 정답 처리를 받을 수 있습니다.

 

 

10254번 : 고속도로

10254번: 고속도로

 

 

도시 n개의 좌표가 주어졌을 때 가장 거리가 먼 두 도시의 좌표를 구하는 문제입니다.

이 문제의 경우 거리가 아닌 좌표를 출력해야 하며, 테스트케이스가 여러 개 존재하여 한 코드에서 여러 번의 테스트케이스를 돌려야 한다는 차이점이 있습니다만, 이는 그렇게 어려운 처리가 아니므로 바로 구현해보도록 하겠습니다.

 

↓ 풀이 코드는 아래의 접은 글에 정리되어 있습니다.

#include <cstdio>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;

struct Coor { long long x, y; };
Coor operator-(Coor a, Coor b) {
    Coor c;
    c.x = a.x - b.x;
    c.y = a.y - b.y;
    return c;
}
vector<Coor> Point;

long long CCW(Coor a, Coor b, Coor c) { return a.x*(b.y-c.y) + b.x*(c.y-a.y) + c.x*(a.y-b.y); }
long long DistSq(Coor a, Coor b) { return (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y); }

bool minCCW(Coor a, Coor b) {
    long long Value = CCW(Point[0], a, b);
    if(Value != 0) return Value > 0;
    else if(a.y != b.y) return a.y < b.y;
    else return a.x < b.x;
}

int main() {
    int T, N;
    scanf("%d", &T);
    for(int t=0; t<T; t++) {
        scanf("%d", &N);
        Point.resize(N);
        for(int i=0; i<N; i++) scanf("%lld %lld", &Point[i].x, &Point[i].y);
        for(int i=1; i<N; i++) {
            if(Point[i].y < Point[0].y || (Point[i].y == Point[0].y && Point[i].x < Point[0].x)) {
                long long temp = Point[0].x;
                Point[0].x = Point[i].x;
                Point[i].x = temp;
                temp = Point[0].y;
                Point[0].y = Point[i].y;
                Point[i].y = temp;
            }
        }
        sort(Point.begin()+1, Point.end(), minCCW);

        stack<Coor> Convex;
        Coor Temp1, Temp2;
        Convex.push(Point[0]);
        Convex.push(Point[1]);
        for(int i=2; i<N; i++) {
            while(Convex.size() >= 2) {
                Temp2 = Convex.top();
                Convex.pop();
                Temp1 = Convex.top();
                if(CCW(Temp1, Temp2, Point[i]) > 0) {
                    Convex.push(Temp2);
                    break;
                }
            }
            Convex.push(Point[i]);
        }
        vector<Coor> Vertex;
        int Size = Convex.size();
        Vertex.resize(Size);
        for(int i=Size-1; i>=0; i--) {
            Vertex[i] = Convex.top();
            Convex.pop();
        }

        int LPoint = 0, RPoint = 0;
        for(int i=0; i<Size; i++) {
            if(Vertex[i].x < Vertex[LPoint].x) LPoint = i;
            if(Vertex[i].x > Vertex[RPoint].x) RPoint = i;
        }
        long long DiaSq = DistSq(Vertex[LPoint], Vertex[RPoint]);
        Coor Origin, Ans1, Ans2;
        Origin.x = 0, Origin.y = 0;
        Ans1 = Vertex[LPoint], Ans2 = Vertex[RPoint];
        for(int i=0; i<Size; i++) {
            if(CCW(Origin, Vertex[(LPoint+1)%Size]-Vertex[LPoint], Vertex[RPoint]-Vertex[(RPoint+1)%Size]) > 0)
                LPoint = (LPoint + 1)%Size;
            else RPoint = (RPoint + 1)%Size;
            if(DistSq(Vertex[LPoint], Vertex[RPoint]) > DiaSq) {
                DiaSq = DistSq(Vertex[LPoint], Vertex[RPoint]);
                Ans1 = Vertex[LPoint], Ans2 = Vertex[RPoint];
            }
        }
        printf("%lld %lld %lld %lld\n", Ans1.x, Ans1.y, Ans2.x, Ans2.y);
    }
}

 

거리가 가장 먼 두 점의 좌표만 저장해서 출력해주면 되므로, Coor type에 해당하는 Ans1과 Ans2를 선언해주고 최대 거리 값이 갱신될 때마다 두 점을 갱신해주기만 하면 됩니다.

테스트케이스의 경우에는 단순히 outer loop를 하나 더 선언해서 구현해주면 됩니다.

 

 

 

풀이를 제출해보면 위와 같이 정답 처리를 받을 수 있습니다.

풀이 시간을 보면 거의 1초에 가깝게 걸렸는데, 이는 테스트케이스들의 데이터가 크고 많이 입력되었음을 의미합니다.

다만 풀이 제한 시간이 어차피 2초로 주어졌기 때문에, 코드를 올바르게 작성했는데 TLE를 받는 경우는 없어보입니다.