[C++ 백준 풀이] 20670번 : 미스테리 싸인 / 3878번 : 점 분리 (볼록다각형 내부의 점 판정)

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge의 20670번 : '미스테리 싸인', 3878번 : '점 분리' 문제에 대한 풀이 코드와 해설을 다루고 있습니다.

 

문제의 난이도는 Solved.ac 기준 Platinum III ~ Platinum II에 해당하며, 문제를 풀이하기 위해 볼록 다각형 내부의 점 판정 알고리즘에 대해 알고 있어야 합니다.

 

[C++ 알고리즘] 다각형 내부의 점 판정 알고리즘 (Point in Convex Polygon)

해당 알고리즘에 대한 설명은 위의 링크에 정리되어 있으니 모르시는 분들은 참고하시면 좋습니다.

 

 

20670번 : 미스테리 싸인

20670번: 미스테리 싸인

 

위의 그림과 같이 외부의 볼록다각형 점들의 좌표, 내부의 볼록다각형 점들의 좌표, 그리고 싸인에 사용될 점의 좌표가 주어졌을 때 싸인이 위의 조건을 만족하면서 생성되는지를 조사하는 문제입니다.

규칙이 복잡하게 작성되어 있지만, 사실 선의 연결보다도 점이 내부의 다각형 밖에 있고 외부의 다각형 안에 있는지만 확인해주면 되는 문제입니다.

따라서 이는 볼록다각형 내부의 점 판정 알고리즘이 사용되는 대표적인 문제임을 알 수 있고, 이를 구현해보도록 하겠습니다.

 

 

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

struct Point { long long x, y; };
Point operator-(Point A, Point B) {
    Point C;
    C.x = A.x - B.x, C.y = A.y - B.y;
    return C;
}
vector<Point> Poly, Poly2, Points;

long long Cross(Point A, Point B, Point C) {
    Point AB = B-A;
    Point AC = C-A;
    return AB.x*AC.y - AB.y*AC.x;
}

bool isInPoly(vector<Point> &Poly, Point P) {
    int Size = Poly.size();
    Point Origin; Origin.x = 0, Origin.y = 0;
    Point LeftV = Poly[Size-1] - Poly[0];
    Point RightV = Poly[1] - Poly[0];
    Point PointV = P - Poly[0];
    if(Cross(Origin, LeftV, PointV) > 0) return false;
    if(Cross(Origin, RightV, PointV) < 0) return false;

    int Left = 1, Right = Size - 1;
    while(Left+1 < Right) {
        int Mid = (Left + Right)/2;
        Point MidV = Poly[Mid] - Poly[0];
        if(Cross(Origin, MidV, PointV) > 0) Left = Mid;
        else Right = Mid;
    }
    Point V1 = P - Poly[Left];
    Point V2 = Poly[Left+1] - P;
    return Cross(Origin, V1, V2) <= 0;
}

int main() {
    int N, M, K;
    scanf("%d %d %d", &N, &M, &K);
    Poly.resize(N), Poly2.resize(M), Points.resize(K);
    for(int i=0; i<N; i++) scanf("%lld %lld", &Poly[i].x, &Poly[i].y);
    for(int i=0; i<M; i++) scanf("%lld %lld", &Poly2[i].x, &Poly2[i].y);
    for(int i=0; i<K; i++) scanf("%lld %lld", &Points[i].x, &Points[i].y);

    int Cnt = 0;
    for(int i=0; i<K; i++)
        if(!isInPoly(Poly, Points[i]) || isInPoly(Poly2, Points[i])) Cnt++;
    if(Cnt == 0) printf("YES");
    else printf("%d", Cnt);
}

 

풀이 코드는 생각보다 길지 않은데, 이는 모든 점들이 반시계 방향으로 정렬된 상태로 입력되도록 조건이 정해져있기 때문에 Convex Hull 알고리즘은 사용될 필요가 없기 때문입니다.

따라서 inIsPoly 함수의 구성만 봐주시면 나머지 부분은 크게 어렵지 않습니다.

알고리즘에 대한 구체적인 작동 원리는 그림을 포함하여 이 포스트의 가장 윗부분에 첨부한 링크에 있으니, 확인해주시면 됩니다.

이 문제에서는 한 점에 대해서 외부 다각형에 대해서는 isInPoly = true이고 외부 다각형에 대해서는 isInPoly = false를 만족하고, 이를 모든 점이 만족해야 합니다.

 

 

 

풀이를 제출해보면 안정적으로 정답 처리를 받을 수 있습니다.

int형의 범위 초과를 제외하고는 딱히 고려해야 할 예외는 없으니 알고리즘만 적절히 사용해주면 됩니다.

 

 

3878번 : 점 분리

 

간단해 보였는데 생각보다 고려해야 할 경우가 많은 문제였습니다.

우선 전반적인 아이디어는 두 그룹의 점들에 Convex Hull 알고리즘을 사용하여 두 개의 볼록다각형을 형성하고, 한 그룹의 점들이 하나라도 다른 그룹의 볼록다각형 내부에 존재하는지 검사하는 것입니다.

그러나 개인적으로는 점이 2개 이하인 상황에서의 위치 관계 판별 때문에 어려움을 겪었습니다.

제가 풀이한 방법은 다음과 같습니다.

 

 

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

struct Point { long long x, y; };
Point operator-(Point A, Point B) {
    Point C;
    C.x = A.x - B.x, C.y = A.y - B.y;
    return C;
}
vector<Point> Black, White;

long long Cross(Point A, Point B, Point C) {
    Point AB = B-A;
    Point AC = C-A;
    return AB.x*AC.y - AB.y*AC.x;
}

bool CrossCompBlack(Point A, Point B) {
    long long Value = Cross(Black[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;
}

bool CrossCompWhite(Point A, Point B) {
    long long Value = Cross(White[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;
}

bool isInPoly(vector<Point> &Poly, Point P) {
    int Size = Poly.size();
    Point Origin; Origin.x = 0, Origin.y = 0;
    Point LeftV = Poly[Size-1] - Poly[0];
    Point RightV = Poly[1] - Poly[0];
    Point PointV = P - Poly[0];
    if(Cross(Origin, LeftV, PointV) > 0) return false;
    if(Cross(Origin, RightV, PointV) < 0) return false;

    int Left = 1, Right = Size - 1;
    while(Left+1 < Right) {
        int Mid = (Left + Right)/2;
        Point MidV = Poly[Mid] - Poly[0];
        if(Cross(Origin, MidV, PointV) > 0) Left = Mid;
        else Right = Mid;
    }
    Point V1 = P - Poly[Left];
    Point V2 = Poly[Left+1] - P;
    return Cross(Origin, V1, V2) <= 0;
}

int main() {
    int T, N, M;
    scanf("%d", &T);
    for(int t=0; t<T; t++) {
        scanf("%d %d", &N, &M);
        Black.resize(N), White.resize(M);
        for(int i=0; i<N; i++) scanf("%lld %lld", &Black[i].x, &Black[i].y);
        for(int i=0; i<M; i++) scanf("%lld %lld", &White[i].x, &White[i].y);

        if(N == 0 || M == 0) {
            printf("YES\n");
            continue;
        }
        else if(N <= 2 && M <= 2) {
            Point A, B, C, D;
            A = B = Black[0], C = D = White[0];
            if(N == 2) B = Black[1];
            if(M == 2) D = White[1];
            long long AB = Cross(A, B, C) * Cross(A, B, D);
            long long CD = Cross(C, D, A) * Cross(C, D, B);
            if(AB == 0 && CD == 0) {
                if(A.x > B.x || (A.x == B.x && A.y > B.y)) swap(A, B);
                if(C.x > D.x || (C.x == D.x && C.y > D.y)) swap(C, D);
                if((C.x < B.x || (C.x == B.x && C.y <= B.y))
                   && (A.x < D.x || (A.x == D.x && A.y <= D.y))) printf("NO\n");
                else printf("YES\n");
            }
            else {
                if(AB <= 0 && CD <= 0) printf("NO\n");
                else printf("YES\n");
            }
            continue;
        }

        for(int i=1; i<N; i++) {
            if(Black[i].y < Black[0].y || (Black[i].y == Black[0].y && Black[i].x < Black[0].x)) {
                long long temp = Black[0].x;
                Black[0].x = Black[i].x;
                Black[i].x = temp;
                temp = Black[0].y;
                Black[0].y = Black[i].y;
                Black[i].y = temp;
            }
        }
        sort(Black.begin()+1, Black.end(), CrossCompBlack);
        vector<Point> PolyBlack;
        PolyBlack.push_back(Black[0]);
        PolyBlack.push_back(Black[1]);
        for(int i=2; i<N; i++) {
            while(PolyBlack.size() >= 2) {
                Point temp2 = PolyBlack.back();
                PolyBlack.pop_back();
                Point temp1 = PolyBlack.back();
                if(Cross(temp1, temp2, Black[i]) > 0) {
                    PolyBlack.push_back(temp2);
                    break;
                }
            }
            PolyBlack.push_back(Black[i]);
        }

        for(int i=1; i<M; i++) {
            if(White[i].y < White[0].y || (White[i].y == White[0].y && White[i].x < White[0].x)) {
                long long temp = White[0].x;
                White[0].x = White[i].x;
                White[i].x = temp;
                temp = White[0].y;
                White[0].y = White[i].y;
                White[i].y = temp;
            }
        }
        sort(White.begin()+1, White.end(), CrossCompWhite);
        vector<Point> PolyWhite;
        PolyWhite.push_back(White[0]);
        PolyWhite.push_back(White[1]);
        for(int i=2; i<M; i++) {
            while(PolyWhite.size() >= 2) {
                Point temp2 = PolyWhite.back();
                PolyWhite.pop_back();
                Point temp1 = PolyWhite.back();
                if(Cross(temp1, temp2, White[i]) > 0) {
                    PolyWhite.push_back(temp2);
                    break;
                }
            }
            PolyWhite.push_back(White[i]);
        }

        int check = 1;
        if(N >= 3) {
            for(int i=0; i<M; i++)
                if(isInPoly(PolyBlack, White[i])) check = 0;
        }
        if(M >= 3) {
            for(int i=0; i<N; i++)
                if(isInPoly(PolyWhite, Black[i])) check = 0;
        }
        if(check) printf("YES\n");
        else printf("NO\n");
    }
}

 

코드가 매우 길어보이지만 대부분의 분량은 Convex Hull을 Black과 White 두 그룹에 대해 사용함으로써 반복되는 코드에 해당합니다.

 

첫 번째로 신경써야 할 부분은 N과 M이 모두 2 이하인 경우입니다.

코드 반복을 줄이기 위해 N 또는 M이 1인 경우는 시작점과 끝점이 같은 선분(= 하나의 점)으로 처리했습니다.

그러면 이제 선분 교차 판정만 하면 되는데, 이 부분이 까다롭습니다.

먼저 두 선분이 같은 직선 위에 있지 않은 경우는 선분 AB에 의한 점 C, D의 외적 값과 선분 CD에 의한 점 A, B의 외적 값을 활용하여 판별하였습니다.

문제가 되는 부분인 두 선분이 같은 직선 위에 있는 경우는, 먼저 swap 함수를 통해 위치 관계를 좌표 크기에 따라 바꿔준 다음 점들의 상대적 위치를 비교함으로써 판별하였습니다.

이 부분은 예외를 찾는 것과 이를 구현하기 위한 해결책을 찾는 것을 동시에 수행하기가 매우 힘들어 다른 이론들을 참고하면서 풀었습니다.

 

두 번째로 신경써야 할 부분은 마지막 isInPoly 호출 부분인데, 하나의 그룹의 점의 수가 3 미만인 경우 isInPoly는 한 쪽 방향으로만 호출을 해주어야 합니다.

 

이렇게 풀이하였을 때 좋은 점은, 하나의 볼록다각형이 다른 볼록다각형의 내부에 들어가있는 경우를 따로 판별하지 않아도 된다는 것입니다.

단점은 코드가 상당히 길어지고 N 또는 M이 2 이하일 때 선분 교차 판별을 따로 해주어야 한다는 것이었습니다.

 

 

 

위의 코드를 제출하면 (코드 길이가 무려 5000B..) 어찌되었든 정답 처리를 받을 수 있습니다.