레이팅 미적용농부 존은 헛간에 근사한 새 착유기를 설치했는데, 전력을 너무 많이 소모해서 가끔 정전이 일어난다! 이런 일이 너무 자주 일어나다 보니 베시는 헛간의 지도를 외워 버렸고, 덕분에 어둠 속에서도 헛간의 출구를 더 쉽게 찾을 수 있다. 하지만 베시는 정전이 헛간을 빨리 빠져나가는 능력에 얼마나 영향을 미치는지 궁금하다. 예를 들어, 어둠 속에서 출구를 찾으려면 얼마나 더 걸어야 할지 알고 싶다.
헛간은 시계 방향 순서로 나열된 정수 꼭짓점 \((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 a 90-degree
angle, but she cannot tell if she is initially standing at vertex 2, 3, or 4.
After taking a step along one edge in the clockwise direction, Bessie either
reaches the exit or can uniquely determine her location based on the length of
this edge. The distances she obtains are:
If starting at vertex 2: she travels 12 units in the dark (1 unit to reach
vertex 3, then 11 units to continue to the exit). She only needs to travel 10
units in a lit barn. This is an extra distance of 2 for this vertex.
If starting at vertex 3: she travels 11 units in both cases.
If starting at vertex 4: she travels 1 unit in both cases.
The worst-case difference over all starting points is therefore 12 - 10 = 2. That
is, Bessie can guarantee that using her strategy, no matter where she starts,
she will travel at most 2 extra units of distance farther in the dark than in the light.