[BOJ 17403]

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

solution

review

BOJ 2254: 감옥 건설과 동일한 문제다.
문제 설명에 있는 고려해야 할 우선순위 3가지는 가능한 한 볼록 껍질을 많이 만들어야 한다는 것과 같다.
따라서 각 정점이 속한 볼록 껍질이 몇 번째로 생성된 볼록 껍질인지만 정보를 저장해서 출력해주면 된다.
구조체 Vertex에서 floor라는 멤버 변수를 별도로 만들어서 관리해줬다.

함수 내에서 별도의 벡터 vertex를 생성하고 관리 가능한 정점이 3개 미만이 될 때까지 무한 루프를 돌려준다.
루프 마지막 부분에서는 스택에서 꺼낸 후 input[].floor에 값을 반영해주자.

while (!s.empty()) {
    chk[vertex[s.top()].idx] = true;
    input[vertex[s.top()].idx].floor = level;
    s.pop();
}

level++;

convexHull()에서 처음 말고도 2번째 while문을 나왔을 때 정점의 개수가 3개 미만인지 체크해줘야 한다.
3개 미만이면 다각형(볼록 껍질)을 만들 수 없기 때문이다.
while문을 나오지 않았을 때 체크하지 않으면 스택에서 팝된 후 값이 반영돼 버린다.
이 부분 때문에 한번 WA를 받았다.