[BOJ 2254]

문제 바로가기 : https://www.acmicpc.net/problem/2254
문제 설명은 위 링크에서 확인해주시길 바랍니다.

solution

review

기존에 썼던 Convex Hull 알고리즘을 가능한 건드리지 않으면서 추가했다.
또한 해당 알고리즘의 코드 주석은 이 문제에선 생략돼 있으니 이해가 안가면 위 링크를 참고!

감옥이 있을 때 감옥 주변을 감싸는 기둥들이 있다. 감옥을 기준으로 몇 개의 볼록 껍질이 생기는지 체크하는 문제다.
볼록 껍질은 당연히 Convex Hull(Graham’s Scan) 알고리즘을 이용해 체크하면 된다.
체크한 볼록 껍질은 체크해놓고 그 다음엔 체크되지 않은 점들을 조사해나가면 된다. 이 방법을 반복한다.
볼록 껍질이 감옥을 포함하는지 여부는 볼록 껍질에 있는 점들과 감옥의 CCW를 확인하면 된다.
하나라도 다르면 감옥이 볼록 껍질 안에 없다는걸 의미하므로 이 때는 while문을 빠져나온다.

bool sameCCW(vector<Vertex> &tmp, Vertex& jail) {
    //마지막에서 처음으로 가는 경우도 체크하기 위함
    tmp.push_back(tmp[0]);

    int key = ccw(tmp[0], tmp[1], jail);
    for (int i = 0; i < tmp.size() - 1; i++) {
        if (ccw(tmp[i], tmp[i + 1], jail) != key) return false;
    }
    return true;
}

정점이 2개 이하일 때는 볼록 껍질이 생성될 수 없으므로 잊지말고 체크하자.