[C++ 백준 풀이] 9240번 : 로버트 후드 / 2049번 : 가장 먼 두 점 / 15028번 : Breaking Biscuits

이 포스트는 프로그래밍 문제 사이트 백준 Online Judge의 9240번 : '로버트 후드' 문제의 풀이 코드와 해설을 다루고 있습니다.

 

문제의 난이도는 Solved.ac 기준 Platinum IV 이상이며, 문제를 풀이하기 위해 Convex Hull 알고리즘과 Rotating Calipers 알고리즘에 대한 이해가 필요합니다.

 

Convex Hull 알고리즘에 대한 설명 : https://restudycafe.tistory.com/386?category=969972 

Rotating Calipers 알고리즘에 대한 설명 : https://restudycafe.tistory.com/401?category=969972 

 

위에 배경 지식을 위한 링크를 첨부하니 공부하실 때 참고하시면 좋습니다.

여기서는 알고리즘을 그대로 적용하여 풀 수 있는 문제들만 다루어보도록 하겠습니다.

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

 

 

9240번 : 로버트 후드

2049번: 가장 먼 두 점

 

주어진 화살의 좌표들 중에서, 가장 거리가 먼 두 화살 사이의 거리를 출력하는 문제입니다.

↓ 풀이 코드는 아래의 접은 글에 정리해두었습니다.

#include <cstdio>
#include <vector>
#include <stack>
#include <algorithm>
#include <cmath>
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;

double Abs(double a) { return a>=0?a:-a; }
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); }
int 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;
    }
    int 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("%.7lf", sqrt(DiaSq));
}

컨벡스 헐 알고리즘을 사용하여 외곽의 점들을 선택해주고, 선택한 점들에 회전하는 캘리퍼스 알고리즘을 사용하여 가장 거리가 먼 두 점을 찾고 그 거리를 구하면 됩니다.

다만 저는 오차 때문에 실수 계산을 하지 않고 거리의 제곱으로 계산을 한 뒤 마지막에 루트를 씌워서 출력하는 방식을 선택하였습니다.

 

 

풀이를 제출해보면 40ms 시간에 모든 테스트케이스를 통과할 수 있습니다.

 

 

2049번 : 가장 먼 두 점

 

이 문제 역시 문제만 보면 이렇게 간단할 수가 없는 문제인데 컨벡스 헐과 회전하는 캘리퍼스를 둘 다 써야하는 문제입니다.

입력 범위가 절댓값 1만 이하의 좌표이므로, (10000, 10000)과 (-10000, -10000)의 거리 제곱을 구해도 대충 8억이 나오므로 int 범위 내에서 해결이 가능합니다.

 

위의 코드를 똑같이 제출해주면 됩니다만, 여기서는 거리의 제곱을 출력하라고 하였으므로 출력부만 거리 제곱으로 바꿔서 출력해주시면 됩니다.

그리고 이런 문제들은 워낙 풀이가 똑같기 때문에, 그냥 복사 붙여넣기 하지 말고 코드를 한 번 다시 써보면서 외우면 좋습니다.

 

 

제출해보면 풀이 소요 시간이 완전히 똑같은데, 이는 테스트케이스가 무엇인지는 정확히는 알 수 없지만, 아마도 입력이 거의 비슷하기 때문이라고 생각됩니다.

 

 

15028번 : Breaking Biscuits

15028번: Breaking Biscuits

 

문제를 쉽게 풀어서 설명하면, 모든 점들을 지나기 위한 최소 폭을 구하는 문제입니다.

이 문제는 단순히 최대 직경을 구하는 것이 아닌, 회전하는 캘리퍼스에서 캘리퍼스 축 간의 최소 거리를 구해야 합니다.

따라서 단순히 부등호를 바꾼다고 해결될 문제가 아니라, 식 자체를 캘리퍼스 사이의 거리를 구하는 식으로 바꿔주어야 합니다.

 

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

#include <cstdio>
#include <vector>
#include <stack>
#include <algorithm>
#include <cmath>
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);
}

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;
}

double DistSq(Coor a1, Coor a2, Coor b) {
    Coor c, d;
    c.x = b.x-a1.x, c.y = b.y-a1.y;
    d.x = a2.x-a1.x, d.y = a2.y-a1.y;
    return ((double)c.x*d.y-(double)c.y*d.x)*((double)c.x*d.y-(double)c.y*d.x)/((double)d.x*d.x+(double)d.y*d.y);
}

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;
    }
    double WidthSq = ((double)Vertex[RPoint].x-Vertex[LPoint].x)*((double)Vertex[RPoint].x-Vertex[LPoint].x);
    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) {
            double TempSq = DistSq(Vertex[LPoint], Vertex[(LPoint+1)%Size], Vertex[RPoint]);
            if(TempSq < WidthSq) WidthSq = TempSq;
            LPoint = (LPoint + 1)%Size;
        }
        else {
            double TempSq = DistSq(Vertex[RPoint], Vertex[(RPoint+1)%Size], Vertex[LPoint]);
            if(TempSq < WidthSq) WidthSq = TempSq;
            RPoint = (RPoint + 1)%Size;
        }
    }
    printf("%.7lf", sqrt(WidthSq));
}

 

역시 캘리퍼스 부분 코드만 보시면 되는데, 점을 갱신하기 전에 점 사이의 거리를 재는 것이 아니라, 벡터와 점 사이의 거리를 구해주면 됩니다.

벡터와 점 사이의 거리는 외적 공식으로 구할 수 있습니다.

위쪽의 DistSq 함수에 공식이 정리되어 있으니, 이를 참고하시면 좋습니다. (물론 이 때 반환값은 거리의 제곱에 해당합니다.)

처음에는 long long으로 했는데 분모 나눗셈 때문에 오차가 발생하므로, double 형으로 풀이해야 합니다.

 

 

 

제출해보면 안정적으로 정답을 받을 수 있습니다.

다만 이 문제는 15420번 : Blowing Candles 문제와 범위만 다를뿐인데, 15420번은 어떤 이유인지 정답 처리를 안 해주네요.

오차 문제인 것 같은데, 이 부분은 최대한 빨리 풀어서 후술하도록 하겠습니다.