회전하는 캘리퍼스를 써도 됩니다. 하지만 구현을 확인해보시면 좋겠습니다. 이렇게 구현하면 캘리퍼스가 결국 지나야 할 점을 모두 지나기는 하겠지만 지나지 말아야 할 점도 정답에 포함됩니다.
참고로 말씀드리면 제가 보통 봤던 구현은 일단 기준변을 잡고 ccw를 이용해서 최대한 앞까지 나간 다음, 기준변을 하나씩 전진시켜 나가면서 반복하는 방식이었습니다. 이 방식을 쓴다면 코드에 반드시 이중 루프가 있어야 합니다.
4
0 0
5 0
20 3
20 10
0
-> should print 6.27, but prints 2.24
seokjin1013 2년 전
AC를 받았긴 했습니다. http://boj.kr/a51e395cbef54be2...
하지만 이 코드에 회전하는 캘리퍼스만 적용시킨 코드는 50%에서 WA를 받습니다. http://boj.kr/4c37578feb524914...
캘리퍼스에 닿는 두 점을 a, b라 하고 각 점에서 반시계 방향으로 이웃하는 점을 a', b'이라 할 때,
max(점 a와 직선 bb'사이의 거리, 점 a'와 직선 bb' 사이의 거리)와
max(점 b와 직선 aa'사이의 거리, 점 b'와 직선 aa' 사이의 거리)를 모든 a, b에 대해 구하고 그 값들의 최솟값을 정답이라 생각했습니다.
수많은 볼록다각형을 그려봐도 캘리퍼스 코드가 왜 오답인지 모르겠습니다.