staphaniek   1년 전

간단한 convex hull 문제라고 생각해서 덤볐는데 의외로 오답이 나네요...ㅠㅠ 혹시 제가 알고있는 방법이 잘못된건지 답좀 주세요....



shjgkwo   1년 전

저도 비슷한 문제를 푸느라 컨벡스 훌을 사용한 적이 있는데요.


제가 쓴 방법은 x좌표 기준으로 정렬을 한뒤(y좌표는 x좌표가 같을때 정렬을 해줌), 가장 왼쪽 아래가 되는 점, 즉 시작점 을 기준으로

stack에 쌓아 나가면서 ccw를 통해 회전 시키는 방법입니다.

stack_size가 2 이상일때에 바로 전전 좌표와 현 좌표 기준으로 바로 전 좌표를 ccw 함수에 넣어서

시계 방향또는 일직선상에 있다면 제거해주고 반시계 방향에 있으면 그대로 입력해줍니다.

shjgkwo   1년 전

저는 이때 시계방향으로 회전할건지 반시계로 회전할건지가 중요한 문제여서 방향까지 잡았지만

일단은 제가 짠 소스중에서 covex hull 부분입니다.

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