파일 업로드

어둠 속 길찾기

profile
실행 시간 제한메모리 제한
2 초512 MB
📃 해결할 문제

지민이는 아파트 단지 안에 새로운 커피 머신을 설치했습니다. 그러나 그것은 너무 많은 전력을 필요로 해서 때때로 전기가 나가게 됩니다! 이런 일이 자주 일어나서 지민이는 아파트 단지의 지도를 외웠습니다. 그래서 어두운 상태에서도 출입구를 쉽게 찾을 수 있습니다. 그러나 그녀는 전력 손실이 어둠 속에서 출입구를 빠르게 찾아내는 능력에 어떤 영향을 줄지 궁금합니다.

아파트 단지는 시계 방향으로 나열된 정수 꼭짓점 (x1,y1)(xn,yn)(x_1, y_1) \ldots (x_n, y_n) 으로 이루어진 간단한 다각형으로 설명됩니다. 그리고 출입구는 (x1,y1)(x_1, y_1) 에 위치해 있습니다. 지민이는 어떤 꼭짓점 (xi,yi)(x_i, y_i)에서 시작합니다. 그녀는 아파트 단지의 둘레를 따라, 시계 방향으로 움직여서 자신이 어떤 꼭짓점에 위치하는지 파악할 수 있을 때까지 움직입니다. 지민이가 정확한 위치를 알게 되면, 그 이후로는 최적의 경로로 출구에 도달합니다.

어느 날, 전기가 나가게 되면 지민은 현재 위치를 잊어버립니다. 그러나 그녀는 아파트 단지의 정확한 지도를 기억하고 있으므로 둘레를 따라 이동하며 느낌을 통해 위치를 알아낼 수 있습니다.

지민이 사용하는 전략을 사용하여 어둠 속에서 어느 위치에서 시작하는지에 따라 여행 거리가 얼마나 증가하는지 알려주세요.

💻 입력

입력의 첫 번째 줄에는 NN (4N2004 \leq N \leq 200)이 포함됩니다. 그 후 NN 줄 각각은, 아파트 단지를 시계방향 순서로 점 (xi,yi)(x_i, y_i)을 설명하는 두 정수를 포함합니다. 이 정수들은 100,000100,000-100,000 \ldots 100,000 범위 내에 있습니다.

🖨️ 출력

문제 문장에서의 전략을 사용하여, 출발 위치가 가장 안 좋은 경우 지민이의 거리가 얼마나 증가하는지를 출력하세요.


💻 예제 입력 1
4
0 0
0 10
1 10
1 0
🖨️ 예제 출력 1
2

💡 힌트

지민이가 출발할 때, 그녀는 특정 꼭짓점에 서 있다는 것을 알고 있지만 정확한 위치는 모릅니다. 그녀의 전략은 시계방향으로 움직이며 그녀의 위치를 파악하는 것입니다.

  • 만약 그녀가 2번 꼭짓점에서 시작한다면, 1단위를 이동해서 3번 꼭짓점에 도착하게 되고, 그 다음에는 11단위를 더 이동해서 출구인 1번 꼭짓점에 도착하게 됩니다. 총 12단위 이동합니다. 반면 불이 있을 때는 2번에서 바로 1번 꼭짓점으로 이동하면 된다는 사실을 알게되니 10단위만 이동하면 됩니다.
  • 3번 꼭짓점에서 시작하는 경우, 그녀는 어두운 상태나 빛이 있을 때나 동일하게 11단위를 이동하게 됩니다.
  • 4번 꼭짓점에서 시작하면, 그녀는 어두운 상태나 빛이 있을 때나 동일하게 1단위만 이동해서 출구에 도착합니다.
  • 출구는 1번 꼭짓점입니다. 지민이가 시작할 때 1번 꼭짓점에 있다면, 추가로 이동할 필요가 없습니다. 그렇기 때문에 1번 꼭짓점은 고려하지 않아도 됩니다.

최악의 경우는 2번 꼭짓점에서 시작할 때이며, 어두운 상태에서 2단위를 더 많이 이동해야 합니다


출처: USACO 2016 January Contest, Gold Problem 3. Lights Out