많이 늦긴 했지만 반례입니다. 회전하는 캘리퍼스 로직을 다시 점검해보시면 좋을 것 같습니다.
10254번 - 고속도로
왜인지는 모르겠지만 소스는 수정이 안 되는군요
추가적으로 설명을 드리자면, (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년 전 1
게시판에 있는 반례를 넣어도 모두 정답이 나오는 것 같습니다. 어디가 문제일까요?