[C++ 백준 풀이] 7420번 : 맹독 방벽 / 6850번 : Cows (Convex Hull 알고리즘)

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge의 7420번 : '맹독 방벽' 문제와 6850번 : 'Cows' 문제의 풀이 코드와 해설을 다루고 있습니다.

 

문제의 난이도는 Solved.ac 기준 Platinum에 해당하며, 문제를 풀이하기 위해 Convex Hull 알고리즘에 대해 알고 있어야 합니다.

 

 

7420번 : 맹독 방벽

 

모든 건물들로부터 L 이상의 거리를 가지는 방벽의 최소 길이를 구하는 문제입니다.

Convex Hull 알고리즘을 이용해 구한 최소 크기의 볼록다각형에 둘레를 추가로 계산해주면 되는 문제입니다.

 

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

#include <cstdio>
#include <vector>
#include <stack>
#include <algorithm>
#include <cmath>
#define Pi 3.14159265358979
using namespace std;

struct Coor { long long x, y; };
vector<Coor> Point;

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

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

double Dist(Coor a, Coor b) {
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

int main() {
    int N, L;
    scanf("%d %d", &N, &L);
    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;
    Convex.push(Point[0]);
    Convex.push(Point[1]);
    for(int i=2; i<N; i++) {
        while(Convex.size() >= 2) {
            Coor temp2 = Convex.top();
            Convex.pop();
            Coor temp1 = Convex.top();
            if(CCW(temp1, temp2, Point[i]) > 0) {
                Convex.push(temp2);
                break;
            }
        }
        Convex.push(Point[i]);
    }

    double Circum = 0;
    Coor First = Convex.top();
    Coor temp1 = Convex.top();
    Coor temp2;
    Convex.pop();
    while(!Convex.empty()) {
        temp2 = Convex.top();
        Convex.pop();
        Circum += Dist(temp1, temp2);
        temp1 = temp2;
    }
    Circum += Dist(temp2, First);
    printf("%.0lf", Circum + 2*Pi*L);
}

 

풀이 코드를 보면 아시겠지만, 추가 거리를 둔다고 해서 새로운 알고리즘이 필요한 것이 아닙니다.

단지 Convex Hull로 구한 꼭짓점들의 둘레에 2*Pi*L(원의 둘레)만 더해주면 답이 됩니다.

 

[C++ 백준 풀이] 2699번 : 격자점 컨벡스헐 / 6194번 : Building the Moat / 10903번 : Wall construction

 

이에 대한 보충 설명은 제가 위의 링크의 포스트에도 정리해두었으니 같이 참고하시면 될 것 같습니다.

 

 

 

풀이를 제출해보면 거의 시간이 소요되지 않고 정답 처리를 받을 수 있습니다.

 

 

6850번 : Cows

 

문제를 해석해보면 소를 가둘 펜스를 칠 때 다각형으로 만들되, 소 한 마리를 키우기 위해 50 제곱미터의 넓이가 필요하다고 합니다.

이 때 주어진 꼭짓점들로 펜스를 짓는다고 할 때 소를 몇 마리 키울 수 있는지를 구하는 문제입니다.

 

 

이는 단순한 Convex Hull 응용 문제로, 우선 Convex Hull로 최대 넓이를 구성하는 볼록 다각형 꼭짓점들을 선택하고, 이들 중 하나를 기준점으로 잡고 2개의 꼭짓점들을 선택하여 삼각형의 넓이들의 합을 구해주면 됩니다.

넓이를 50으로 나눈 몫이 키울 수 있는 소의 수가 되므로, 이를 계산해주기만 하면 됩니다.

 

#include <cstdio>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
 
struct Coor { long long x, y; };
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 + b.x*c.y + c.x*a.y - a.x*c.y - b.x*a.y - c.x*b.y;
}
 
bool minCCW(Coor a, Coor b) {
    long long Value = CCW(Point[0], a, b);
    if(Value) return Value > 0;
    else if(a.y != b.y) return a.y < b.y;
    else return a.x < b.x;
}
 
int main() {
    int N;
    double Area = 0;
    Coor temp1, temp2, First, Pop1, Pop2;
    stack<Coor> Convex;
    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);
    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]);
    }
    First = Convex.top();
    Convex.pop();
    Pop1 = Convex.top();
    Convex.pop();
    while(!Convex.empty()) {
        Pop2 = Convex.top();
        Convex.pop();
        Area += 0.5 * Abs((double)CCW(First, Pop1, Pop2));
        Pop1 = Pop2;
    }
    printf("%d", (int)(Area/50));
}
 

 

풀이 코드는 위와 같고, 제가 위에 그린 그림 그대로 코드로 구현한 것입니다.

컨벡스 헐 알고리즘을 사용하면 외곽의 점들이 스택에 저장되기 때문에, 다시 스택에서 점들을 하나씩 빼면서 삼각형을 만들어주면 됩니다.

스택에서 가장 먼저 뺀 점을 First로 잡고, 1개씩 빼면서 인접한 삼각형의 넓이들을 계산해서 합해주었습니다.

 

 

채점해보면 4ms의 시간이 소요되고 모든 테스트케이스를 통과할 수 있습니다.