재채점했습니다.
1708번 - 볼록 껍질
현재 제가 "데이터를 추가한 사람" 이 아니라 "문제를 만든 사람"에 들어가 있습니다. 위치 수정 부탁드립니다.
제 코드를 읽어보신 것 같은데, 그 코드의 주석대로 따라가 보세요.
우선 y좌표가 최소인 점 중 x좌표가 최소인 점은 볼록 껍질에 반드시 포함되므로, 그 점을 중심으로 나머지 점들을 정렬해야 합니다.
점들을 극좌표 기준 0도를 시작으로 반시계방향 순서대로 정렬해주고(CCW 이용),
극좌표 각이 같은 경우 "중심점을 기준으로 유클리드상 거리가 더 작은 점이 먼저 오게"끔 정렬을 해 줍니다.
(double형 실수는 오차로 인해 계산 및 정렬에는 적절하지 않습니다. 또 x축에 수직인 점의 집합들이 있으면 처리가 곤란하기도 하고요. 그래서 CCW를 이용합니다.)
또, 볼록 껍질의 정의상 첫 번째 점부터 시작해서 모든 점을 다 돌고 마지막에 처음 시작한 점으로 돌아와야 합니다.
그래서 1~n번 점까지 돌고 마지막 (n+1)번째로 1번을 다시 돌아서 껍질을 닫아줍니다.
그러면 스택에 1번 점은 두 번 들어간 형태가 되므로, 최종 정답에서 1을 빼줘야 합니다.
제 코드에도 나와 있는 내용이니, 이 글과 함께 코드를 살펴보고 답을 고쳐보세요. 모르겠는 부분은 언제든 질문 주세요.
댓글을 작성하려면 로그인해야 합니다.
rootsquare 4년 전 1
제출번호 39063148
https://www.acmicpc.net/source...
여러 개의 점이 한 직선 위에 있을 때 답을 바르게 출력하지 못하는 코드가 맞았다고 합니다.
아래에 제시된 입출력을 추가해주세요.