[C++ 백준 풀이] Point in Convex Polygon 정리 코드 (11686번 : Saint John Festival)

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge의 11686번 : 'Saint John Festival' 문제의 풀이 코드와 해설을 다루고 있습니다.

 

문제의 난이도는 Solved.ac 기준 Platinum II에 해당하며, 문제를 풀이하기 위해 Convex Hull 알고리즘과 볼록다각형 내부의 점 판정 알고리즘(O(log N))에 대해 알아야합니다.

 

이 포스트에 볼록 다각형 내부의 점 판정 알고리즘을 깔끔하게 정리한 코드를 정리합니다.

 

 

11686번 : Saint John Festival

 

Large sky lanterns들 중에서 3개를 선택하여 만들 수 있는 삼각형에 포함되는 small sky lanterns의 수를 구하는 문제입니다.

 

Convex Hull 알고리즘을 사용하여 가장 큰 볼록다각형을 선택하면 볼록다각형 내부의 어떤 점을 선택해도 이 점을 포함하는 삼각형을 만들 수 있으므로 결국 볼록다각형 내부의 점의 수를 구하는 문제로 치환하여 풀 수 있습니다.

 

이를 구현한 코드를 아래에 정리하겠습니다.

 

 

#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> Large;

long long Cross(Point A, Point B, Point C) {
    long long Value = A.x*(B.y-C.y) + B.x*(C.y-A.y) + C.x*(A.y-B.y);
    if(Value > 0) return 1;
    else if(Value < 0) return -1;
    else return 0;
}

bool CrossCompare(Point A, Point B) {
    long long Value = Cross(Large[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 N, M;
    scanf("%d", &N);
    Large.resize(N);
    for(int i=0; i<N; i++) scanf("%lld %lld", &Large[i].x, &Large[i].y);
    for(int i=1; i<N; i++)
        if(Large[i].y < Large[0].y || (Large[i].y == Large[0].y && Large[i].x < Large[0].x))
            swap(Large[0], Large[i]);
    sort(Large.begin()+1, Large.end(), CrossCompare);

    vector<Point> Poly;
    Poly.push_back(Large[0]);
    Poly.push_back(Large[1]);
    for(int i=2; i<N; i++) {
        while(Poly.size() >= 2) {
            Point Temp2 = Poly.back();
            Poly.pop_back();
            Point Temp1 = Poly.back();
            if(Cross(Temp1, Temp2, Large[i]) > 0) {
                Poly.push_back(Temp2);
                break;
            }
        }
        Poly.push_back(Large[i]);
    }

    scanf("%d", &M);
    int Cnt = 0;
    for(int i=0; i<M; i++) {
        long long x, y;
        scanf("%lld %lld", &x, &y);
        Point P;
        P.x = x, P.y = y;
        if(isInPoly(Poly, P)) Cnt++;
    }
    printf("%d", Cnt);
}

 

큰 랜턴들의 좌표를 먼저 입력받고, 이들을 벡터에 저장합니다.

이후 Convex Hull 알고리즘을 사용하여 가장 큰 볼록다각형의 꼭짓점에 해당하는 점들만 반시계 방향으로 추출합니다.

다음으로 작은 랜턴들의 좌표를 하나씩 입력받아, isInPoly 함수에서 이 점이 큰 랜턴들이 구성하는 볼록다각형에 포함되는 점인지를 판정합니다.

이 때 볼록다각형의 경계선 상에 존재하는 점 역시 포함해주어야 하므로 return Cross 값을 >= 0으로 설정해줍니다.

 

 

 

풀이를 제출하면 위와 같이 32ms 시간으로 정답 처리를 받을 수 있습니다.

저의 경우에는 점 판정하고 오버플로우 개념이 헷갈리다 보니까 틀린 이후에도 엉뚱한 곳을 계속 고치거나 없는 반례를 계속 찾고 있었습니다.

오개념이나 헷갈리는 것이 없도록 더 열심히 공부해야겠습니다.