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

이 포스트는 프로그래밍 문제 사이트 백준 Online Judge의 2699번 : '격자점 컨벡스헐', 6194번 : 'Building the Moat', 10903번 : 'Wall construction' 문제의 풀이 코드와 해설을 다루고 있습니다.

 

문제의 난이도는 Solved.ac 기준 Platinum에 해당하며, 문제를 풀이하기 위해 Convex Hull 알고리즘이 응용되므로, 이에 대해 알고 있으면 좋습니다.

 

 

2699번 : 격자점 컨벡스헐

 

먼저 테스트케이스의 수가 입력되면, 해당 테스트케이스 수만큼의 아래의 처리를 수행해야 합니다.

N개의 점에 대해 가장 큰 볼록다각형(꼭짓점들로 이어진 볼록다각형이 나머지 점들을 모두 내부에 포함하는 다각형)을 구성하는 꼭짓점들의 수를 출력하고, 이들 중 y좌표가 가장 큰 (동률일 경우 x좌표가 가장 작은) 점을 선두로 나머지 점들을 출력하는 문제입니다.

 

 

 

제가 임의로 편집한 예제 입출력 1번만 보면, 먼저 테스트케이스의 수 4가 입력되고 아래에 각 케이스들의 입력이 주어집니다. (이미지는 편집되었지만 아래로 3개의 케이스에 대한 입력이 더 존재합니다.)

25개는 점의 수이고, 한 줄에 5개씩 총 5줄로 점들의 좌표가 입력됩니다.

 

그러면 이들 중 가장 큰 볼록다각형을 구성하는 점들을 찾아 그 개수를 출력하면 여기서는 10개이고, 이제 y좌표가 가장 크고 그들 중 x좌표가 가장 작은 (4, 9)를 먼저 출력하는 것을 알 수 있습니다.

이를 순서로 나머지 점들을 다각형의 방향을 따라서 순서대로 출력해주면 됩니다.

(보통은 반시계 방향으로 스택에 들어가니, 이를 역순으로 뽑아서 출력하면 시계방향이 될 것입니다.)

 

그럼 이제 Convex Hull 알고리즘을 사용하여 위의 문제를 풀이해보겠습니다.

 

 

#include <cstdio>
#include <vector>
#include <stack>
#include <algorithm>
#define INF 10000
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;
}
 
int main() {
    int T, N;
    scanf("%d", &T);
    for(int i=0; i<T; i++) {
        int cnt = 0, xMin = INF, yMax = -INF, first = 0;
        stack<Coor> Convex;
        vector<Coor> Ans;
        scanf("%d", &N);
        Point.resize(N), Ans.resize(N);
        for(int j=0; j<N; j++) scanf("%lld %lld", &Point[j].x, &Point[j].y);
        for(int j=1; j<N; j++) {
            if(Point[j].y < Point[0].y || (Point[j].y == Point[0].y && Point[j].x < Point[0].x)) {
                long long temp = Point[0].x;
                Point[0].x = Point[j].x;
                Point[j].x = temp;
                temp = Point[0].y;
                Point[0].y = Point[j].y;
                Point[j].y = temp;
            }
        }
        sort(Point.begin()+1, Point.end(), minCCW);
        Convex.push(Point[0]);
        Convex.push(Point[1]);
        for(int j=2; j<N; j++) {
            while(Convex.size() >= 2) {
                Coor temp2 = Convex.top();
                Convex.pop();
                Coor temp1 = Convex.top();
                if(CCW(temp1, temp2, Point[j]) > 0) {
                    Convex.push(temp2);
                    break;
                }
            }
            Convex.push(Point[j]);
        }
        printf("%ld\n", Convex.size());
        while(!Convex.empty()) {
            Coor Pop = Convex.top();
            Convex.pop();
            if(Pop.y > yMax || (Pop.y == yMax && Pop.x < xMin)) {
                yMax = Pop.y;
                xMin = Pop.x;
                first = cnt;
            }
            Ans[cnt].x = Pop.x, Ans[cnt++].y = Pop.y;
        }
        for(int i=first; i<cnt; i++) printf("%lld %lld\n", Ans[i].x, Ans[i].y);
        for(int i=0; i<first; i++) printf("%lld %lld\n", Ans[i].x, Ans[i].y);
    }
}
 

 

일반적인 Convex Hull 알고리즘대로, 가장 아래 왼쪽 점을 잡아서 그 점을 기준으로 아래 왼쪽에 있는 점을 잡아 연결하여 기준 선분을 만들고 그 선분으로부터 반시계 방향으로 가까운 순으로 점들을 정렬했습니다.

그 다음 정렬된 점들을 순서대로 스택에 집어넣으면서 CCW 알고리즘을 이용해 세 점의 외적이 양수, 즉 반시계 방향에 위치하여 볼록한지를 확인하고 아니면 스택에서 제외시키는 과정을 반복하여 검사를 진행하였습니다.

 

이 문제에서는 특히 첫 번째 점을 다르게 잡아주어야 하기 때문에, 배열에 저장 하면서 y 좌표가 최대인 점 그 중에서도 x 좌표가 최소인 점을 찾아서 그 번호를 first에 저장하였습니다.

배열에 모든 좌표를 옮긴 이후에는 first부터 점들을 순차적으로 출력하여 출력 조건이 만족되도록 구현하였습니다.

 

 

 

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

문제에 예제를 많이 주었기 때문에, 4개의 예제를 확인해보면서 코드를 제출하기 전에 어디서 틀렸는지를 미리 확인해볼 수 있어서 좋았습니다.

입력 좌표의 범위가 절댓값 20 이하로 아주 작기 때문에, 소요 시간이 거의 없는 것을 확인할 수 있습니다.

이를 고려하면 거의 노가다로도 해결이 어떻게든 가능하기는 했을 것 같습니다.

 

 

6194번 : Building the Moat

 

문제를 해석해보면, 여러 개의 연못의 좌표가 주어졌을 때 모든 연못들을 포함하는 가장 작은 다각형 둘레의 길이를 출력하는 문제입니다.

연못을 포함하는 가장 작은 다각형은, 결국 가장 바깥쪽의 연못을 꼭짓점으로 하여 만들어지는 볼록다각형이므로 이는 Convex Hull 알고리즘 문제임을 알 수 있습니다.

따라서 위의 문제와 비슷한 방법으로 구현이 가능합니다.

 

 

#include <cstdio>
#include <vector>
#include <stack>
#include <algorithm>
#include <cmath>
#define INF 1000000001
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 - 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) 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 Ans = 0;
    Coor First, Prev, Cur;
    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) {
            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]);
    }
    First = Convex.top();
    Prev = Convex.top();
    Convex.pop();
    while(!Convex.empty()) {
        Cur = Convex.top();
        Convex.pop();
        Ans += sqrt((Cur.x-Prev.x)*(Cur.x-Prev.x)+(Cur.y-Prev.y)*(Cur.y-Prev.y));
        Prev = Cur;
    }
    Ans += sqrt((Cur.x-First.x)*(Cur.x-First.x)+(Cur.y-First.y)*(Cur.y-First.y));
    printf("%.2lf", Ans);
}
 

 

대부분의 코드는 일반적인 Convex Hull 알고리즘 구현과 같고, 마지막 부분에서 변의 길이를 구해주면 됩니다.

다만 첫 번째 점은 마지막 점과도 연결이 되어야하므로, First Point에 따로 저장해주고, 나머지 인접한 변들은 가장 최근에 Pop한 2개의 점 사이에 피타고라스 정리를 사용하여 거리를 더해줍니다.

마지막에 첫 점과 마지막 점 사이의 거리를 더해주고 출력해주면 정답을 얻을 수 있습니다.

 

 

 

이 문제는 단순히 Convex Hull 구현만 하면 예외가 없기 때문에 쉽게 해결할 수 있는 문제였습니다.

 

 

10903번 : Wall construction

 

이 문제 역시 위의 문제와 거의 비슷하지만, 기둥의 둘레까지 포함해서 기둥을 둘러싼 둘레를 구하는 문제입니다.

그런데 이 문제는 잘 생각해보면, 답을 아주 간단하게 구할 수 있습니다.

 

 

 

발그림이라 그림이 좀 구린데, 잘 생각해보면 기존의 정점들을 잇는 다각형의 둘레에서 기둥까지 포함한 둘레는 빨간색의 길이는 같음을 알 수 있습니다.

그리고 나머지 파란색의 길이를 합치면 결국 기둥 하나의 둘레가 되므로, 정점끼리 이어서 만들어진 볼록다각형에 기둥 한 개의 둘레만 추가하면 됨을 알 수 있습니다.

 

 

#include <cstdio>
#include <vector>
#include <stack>
#include <algorithm>
#include <cmath>
#define INF 1000000001
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 - 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) return Value > 0;
    else if(a.y != b.y) return a.y < b.y;
    else return a.x < b.x;
}
 
int main() {
    int N, R;
    double Ans = 0;
    Coor First, Prev, Cur;
    stack<Coor> Convex;
    scanf("%d %d", &N, &R);
    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) {
            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]);
    }
    First = Convex.top();
    Prev = Convex.top();
    Convex.pop();
    while(!Convex.empty()) {
        Cur = Convex.top();
        Convex.pop();
        Ans += sqrt((Cur.x-Prev.x)*(Cur.x-Prev.x)+(Cur.y-Prev.y)*(Cur.y-Prev.y));
        Prev = Cur;
    }
    Ans += sqrt((Cur.x-First.x)*(Cur.x-First.x)+(Cur.y-First.y)*(Cur.y-First.y));
    printf("%.9lf", Ans+2*R*3.141592653);
}
 

 

 

풀이를 제출해보면 위와 같이 거의 시간이 소요되지 않고 정답을 받을 수 있음을 확인할 수 있습니다.