redcube231   3년 전

생에 첫 플레티넘 정답이라 기뻐서 코드를 정리하다가 문제점을 발견해서 말씀드립니다.

모든 코드를 올려버리면 부정행위가 될 수 있으므로 일부 코드만 올립니다.


제가 풀이한 방식부터 설명드립니다.

광원으로부터 나무의 8개 점을 향하는 모든 벡터와 z = 0 인 평면의 교점 8개를 찾아 그라함 스캔을 돌리는 방식으로 볼록 껍질을 찾습니다.

볼록 껍질로 이루어진 그림자의 넓이가 곧 정답입니다.


나무가 바닥에 붙어있고 광원이 나무를 위에서 비춘다고 하더라도 그림자는 생기게 됩니다만, 바닥과 붙어있는 면은 그림자로 칠 수 없습니다.

반례를 처리하기 위해 "나무의 좌표 중 z = 0인 점이 있으면 바닥과 접하는 면의 넓이를 구하고 맨 나중에 뺀다" 라고 알고리즘을 최종 구성했습니다.

문제는 제가 생각해낸 반례를 처리하다가 저지른 실수에서 나왔습니다.

그라함 스캔으로 찾은 넓이를 미리 구하고 접한 면을 뺴야하는데, 먼저 외적으로 구한 넓이(그림자 넓이의 2배가 됨)에서 접한 면의 넓이를 빼고 반으로 가른 겁니다. 근데 그게 정답 처리가 되었습니다.

물론 올바른 방법으로 구해도 정답 처리가 되었습니다.

제가 어쩌다가 120줄짜리 코드를 장난으로 짜서 어쩌다가 맞은 게 아닌 이상 문제의 데이터가 부족하다고 생각됩니다.

아마도 나무가 바닥에 붙은 상황이 데이터에 없는 것 같습니다.

검토를 요청드립니다.

핵심코드를 첨부합니다.

redcube231   3년 전

제 코드의 반례입니다.

-1 -1 0 1 1 2

0 0 5

정답

7.111111..

오답

9.111111..

바닥에 붙은 2 * 2 * 2 크기 나무가 가운데 5 높이의 광원으로부터 만드는 그림자의 넓이는 7.111111..로 계산되나 틀린 코드로는 9.111111..이 계산됩니다.

저는 나무의 좌표가 양수든 음수든 계산이 되도록 만들었으나 문제의 데이터로 넣기 위해서는

1 1 0 3 3 2

2 2 5

처럼 위치를 움직여서 적용하먼 됩니다.

preview

정답

preview

틀린 코드 (그러나 정답 처리)

bluestaxks   3년 전

2*2*2 정육면체 위에 0,0,5 위치에 빛이 있으면 그림자 넓이는 11.1111111111111 아닌가요?

redcube231   3년 전

바닥에 붙은 부분은 그림자에서 제외해서 11.11111... - 4 = 7.11111... 가 됩니다.

bluestaxks   3년 전

바닥에 붙은 부분이 그림자가 아니라고 생각하는 이유는 모르겠지만 문제 조건에선 나무가 바닥에 붙지 않습니다

redcube231   3년 전

문제에서 자연수라고 명시했기 때문에 0은 제외인 걸 알고 있었지만 역시 문제에서 '떠있을 수도 있다'라고 제시해서 붙은 게 기본값일 거라고 생각했습니다. 그래서 생긴 오해 같습니다.

바닥에 붙은 부분이 그림자인가?는 철학의 영역으로 넘어가는 주제가 아닌가 합니다ㅋㅋㅋ....

댓글을 작성하려면 로그인해야 합니다.