실행 시간 제한 | 메모리 제한 |
---|---|
2 초 | 512 MB |
지민이는 아파트 단지 안에 새로운 커피 머신을 설치했습니다. 그러나 그것은 너무 많은 전력을 필요로 해서 때때로 전기가 나가게 됩니다! 이런 일이 자주 일어나서 지민이는 아파트 단지의 지도를 외웠습니다. 그래서 어두운 상태에서도 출입구를 쉽게 찾을 수 있습니다. 그러나 그녀는 전력 손실이 어둠 속에서 출입구를 빠르게 찾아내는 능력에 어떤 영향을 줄지 궁금합니다.
아파트 단지는 시계 방향으로 나열된 정수 꼭짓점 으로 이루어진 간단한 다각형으로 설명됩니다. 그리고 출입구는 에 위치해 있습니다. 지민이는 어떤 꼭짓점 에서 시작합니다. 그녀는 아파트 단지의 둘레를 따라, 시계 방향으로 움직여서 자신이 어떤 꼭짓점에 위치하는지 파악할 수 있을 때까지 움직입니다. 지민이가 정확한 위치를 알게 되면, 그 이후로는 최적의 경로로 출구에 도달합니다.
어느 날, 전기가 나가게 되면 지민은 현재 위치를 잊어버립니다. 그러나 그녀는 아파트 단지의 정확한 지도를 기억하고 있으므로 둘레를 따라 이동하며 느낌을 통해 위치를 알아낼 수 있습니다.
지민이 사용하는 전략을 사용하여 어둠 속에서 어느 위치에서 시작하는지에 따라 여행 거리가 얼마나 증가하는지 알려주세요.
입력의 첫 번째 줄에는 ()이 포함됩니다. 그 후 줄 각각은, 아파트 단지를 시계방향 순서로 점 을 설명하는 두 정수를 포함합니다. 이 정수들은 범위 내에 있습니다.
문제 문장에서의 전략을 사용하여, 출발 위치가 가장 안 좋은 경우 지민이의 거리가 얼마나 증가하는지를 출력하세요.
4 0 0 0 10 1 10 1 0
2
지민이가 출발할 때, 그녀는 특정 꼭짓점에 서 있다는 것을 알고 있지만 정확한 위치는 모릅니다. 그녀의 전략은 시계방향으로 움직이며 그녀의 위치를 파악하는 것입니다.
최악의 경우는 2번 꼭짓점에서 시작할 때이며, 어두운 상태에서 2단위를 더 많이 이동해야 합니다