ezh8n   1년 전

게시판에 있는 반례를 넣어도 모두 정답이 나오는 것 같습니다. 어디가 문제일까요?

hyper1423   1년 전

많이 늦긴 했지만 반례입니다. 회전하는 캘리퍼스 로직을 다시 점검해보시면 좋을 것 같습니다.

hyper1423   1년 전

왜인지는 모르겠지만 소스는 수정이 안 되는군요
추가적으로 설명을 드리자면, (0, 0)과 (95, -30) 사이의 거리는 약 99.62429, (0, 0)과 (100, 0) 사이의 거리는 100입니다.

회전하는 캘리퍼스에서 i와 j를 거리가 최대가 되도록 잡는 것은 정답을 보장하지 않습니다. (저도 이 문제를 풀 때 당했던 케이스라...)

반례를 보시면 현재 알고리즘은 (0, 0) -> (52, 58)보다 (0, 0) -> (56, 54)가 짧기 때문에 중간에 j의 진행이 막혀버려 진짜 최대 거리인 (0, 0) -> (100, 0)을 찾지 못합니다. 마찬가지로, (100, 0) -> (95, -30)보다 (100, 0) -> (91, -29)가 짧기 때문에 진짜 최대 거리인 (100, 0) -> (0, 0)을 찾지 못합니다. 결국 (95, -30) -> (0, 0)을 출력하지만, 이는 정답이 아닙니다.

ezh8n   1년 전

해당 부분 코드를 수정해서 풀었는데 이제 다른 이유로 틀린 것 같습니다.

hyper1423   1년 전

마지막으로 제출하신 코드를 확인해봤는데, 각도 정렬 과정에 문제가 생긴 것 같습니다.
현재 A를 정렬하는 과정에 사용되는 비교함수에서 기준점으로 A[0]이 매번 참조되고 있는데, std::sort 중에 A[0]의 값이 고정되어 있다는 보장이 없기 때문에 정의되지 않은 동작이 발생합니다. 실제로 비교함수에 출력문을 넣어서 테스트해본 결과 실행 중에 A[0]의 값이 계속 바뀌는 걸 확인할 수 있었습니다.
아마 A[0]의 값을 다른 변수에 저장해놓고 쓰셔야 할 것 같습니다.

ezh8n   1년 전

정렬하는 구간을 A[1]부터 A[n-1]까지로 바꿔서 해결하였습니다. 감사합니다.

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