레이팅 미적용농부 존은 헛간에 근사한 새 착유기를 설치했는데, 전력을 너무 많이 소모해서 가끔 정전이 일어난다! 이런 일이 너무 자주 일어나다 보니 베시는 헛간의 지도를 외워 버렸고, 덕분에 어둠 속에서도 헛간의 출구를 더 쉽게 찾을 수 있다. 하지만 베시는 정전이 헛간을 빨리 빠져나가는 능력에 얼마나 영향을 미치는지 궁금하다. 예를 들어, 어둠 속에서 출구를 찾으려면 얼마나 더 걸어야 할지 알고 싶다.
헛간은 시계 방향 순서로 나열된 정수 꼭짓점 \((x_1, y_1) \ldots (x_n, y_n)\)을 갖는 단순(자기 자신과 교차하지 않는) 다각형으로 표현된다. 변은 수평(x축과 평행)과 수직(y축과 평행)이 번갈아 나타나며, 첫 변은 어느 쪽이어도 된다. 출구는 \((x_1, y_1)\)에 있다. 베시는 헛간 안의 어떤 꼭짓점 \((x_i, y_i)\) (\(i > 1\))에 서 있다. 베시는 헛간의 둘레를 따라 시계 방향 또는 반시계 방향으로만 걸을 수 있으며, 꼭짓점에 도달할 때마다 방향을 바꿀 수 있다. 목표는 최소 거리를 이동해 출구에 도달하는 것이다. 불이 켜져 있을 때는 물론 비교적 쉽다. 현재 위치에서 출구까지 시계 방향과 반시계 방향 중 더 짧은 쪽으로 이동하면 되기 때문이다.
어느 날 정전이 일어났고, 베시는 당황해서 자신이 어느 꼭짓점에 서 있는지 잊어버렸다. 다행히 헛간의 정확한 지도는 아직 기억하고 있으므로, 걸어 다니며 촉각을 이용해 자신의 위치를 알아낼 수도 있다. 꼭짓점에 서 있을 때는 (처음 서 있던 꼭짓점 포함) 그곳이 왼쪽으로 꺾이는지 오른쪽으로 꺾이는지 느낄 수 있고, 그 꼭짓점이 출구인지도 알 수 있다. 헛간의 변을 따라 걸을 때는 변 전체를 다 걷고 나면 그 변의 정확한 길이를 알 수 있다. 일반적으로 베시는 자신이 어디 있는지 판단하기에 충분한 정보를 얻을 때까지 시작 꼭짓점 주변을 전략적으로 더듬으며 이동하고, 그 시점부터는 남은 거리를 최소로 하여 출구에 도달하는 방법을 쉽게 알아낼 수 있다.
어둠 속에서의 이동이 불이 켜진 헛간에서의 이동보다, 최악의 경우(가능한 모든 시작 꼭짓점에 대해) 이동 거리가 늘어나는 양의 가능한 최솟값을 구하도록 베시를 도와주자. 두 경우 모두 베시는 최적 전략에 따라 움직인다고 가정한다. 정전 상황에서의 "최적" 전략이란 이 최악의 경우 추가량을 최소화하는 전략이다.
출제자: Brian Dean
출제자: Brian Dean
입력의 첫째 줄에 \(N\) (\(4 \leq N \leq 200\))이 주어진다. 다음 \(N\)개의 줄에 각각 두 정수가 주어지며, 헛간 둘레를 시계 방향으로 도는 순서의 점 \((x_i, y_i)\)를 나타낸다. 이 정수들은 \(-100,000 \ldots 100,000\) 범위이다.
어둠 속에서의 베시의 최적 이동 거리가 불이 켜진 헛간에서의 최적 이동 거리보다 길어지는, 최악의 경우 추가량의 가능한 최솟값을 출력한다. 최악의 경우는 베시가 시작할 수 있는 모든 꼭짓점에 대해 취한다.
lightsout.in · 출력을 쓸 파일 lightsout.out4
0 0
0 10
1 10
1 02In this example, Bessie can feel that she is initially standing at an inward
bend, however since in this example all corners are inward bends this tells her
little information.
One optimal strategy is to just travel clockwise. This is optimal is she starts at vertex 3 or 4 and only adds 2 units of distance if she starts at vertex 2.
riseoj 작성
출처 올림피아드 > USACO > 2015-2016 > January > Platinum