rootsquare   4년 전

제출번호 39063148

https://www.acmicpc.net/source...

여러 개의 점이 한 직선 위에 있을 때 답을 바르게 출력하지 못하는 코드가 맞았다고 합니다.

아래에 제시된 입출력을 추가해주세요.

startlink   4년 전

재채점했습니다.

rootsquare   4년 전

@startlink

현재 제가 "데이터를 추가한 사람" 이 아니라 "문제를 만든 사람"에 들어가 있습니다. 위치 수정 부탁드립니다.

startlink   4년 전

수정했습니다.

hemi0213   4년 전

코드 지적 정말 감사합니다.

코드에서 graham scan시 일직선 상에 놓여있는 여러 개의 점들 중 최종적으로 볼록 껍질에 포함되는 경우 양 끝 점만 포함하지 않나요?

위의 코드를 실행하여 테스트 케이스를 대입 시 결과값이 4로 나오는 것 같습니다.

위의 테스트 케이스를 돌려서 스택의 좌표값을 확인해본 결과 (-3,0), (0,3), (3,0), (0,-3) 이었습니다.

혹시 제가 잘못 생각하는 경우가 있을까요? 감사합니다.

rootsquare   4년 전

@hemi0213

제 코드를 읽어보신 것 같은데, 그 코드의 주석대로 따라가 보세요.

우선 y좌표가 최소인 점 중 x좌표가 최소인 점은 볼록 껍질에 반드시 포함되므로, 그 점을 중심으로 나머지 점들을 정렬해야 합니다.

점들을 극좌표 기준 0도를 시작으로 반시계방향 순서대로 정렬해주고(CCW 이용),

극좌표 각이 같은 경우 "중심점을 기준으로 유클리드상 거리가 더 작은 점이 먼저 오게"끔 정렬을 해 줍니다.

(double형 실수는 오차로 인해 계산 및 정렬에는 적절하지 않습니다. 또 x축에 수직인 점의 집합들이 있으면 처리가 곤란하기도 하고요. 그래서 CCW를 이용합니다.)


또, 볼록 껍질의 정의상 첫 번째 점부터 시작해서 모든 점을 다 돌고 마지막에 처음 시작한 점으로 돌아와야 합니다.

그래서 1~n번 점까지 돌고 마지막 (n+1)번째로 1번을 다시 돌아서 껍질을 닫아줍니다.

그러면 스택에 1번 점은 두 번 들어간 형태가 되므로, 최종 정답에서 1을 빼줘야 합니다.


제 코드에도 나와 있는 내용이니, 이 글과 함께 코드를 살펴보고 답을 고쳐보세요. 모르겠는 부분은 언제든 질문 주세요.

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