백준 25997 (C++) Failing Flagship

최초 업로드: 2025-09-21 15:40:12

최근 수정 시간: 2025-09-21 15:40:12

게시자: rlatjwls3333

카테고리: 백준

# [Silver II] Failing Flagship

[문제 링크](https://www.acmicpc.net/problem/25997)

## 문제 설명

Ahoy! You are sailing towards the next "Boats Are Pretty Cool" convention to sell your latest gadget: a new type of compass.

On a normal compass, it is difficult to read off the precise wind direction. However, your new type of compass lets you read off wind directions to a much higher precision! The display can display strings of at most $1000$ characters.

Unfortunately, you have encountered some bad weather. After a few hours of heavy winds and big waves, you can finally look at your compass again. You read off the wind direction $X$ you are going and know in which wind direction $Y$ you need to go. However, to make the ship turn you have to enter the degrees of the angle the ship has to make in the control system. What is the smallest turn, in degrees, you have to make to get back on the right course?

Figure F.1: Wind directions

The conversion of a wind direction to degrees goes as follows. The four basic wind directions are N, E, S, and W pointing at $0$, $90$, $180$, and $270$ degrees, respectively. There are also four wind directions consisting of two letters: NE, SE, SW, and NW, pointing at $45$, $135$, $225$, and $315$ degrees, respectively.

A wind direction can also consist of $k\geq 3$ letters $l_1l_2\ldots l_k$. In that case, the last two letters indicate one of the four two-letter wind directions, i.e., $l_{k-1}l_k \in \{\text{NE}, \text{SE}, \text{SW}, \text{NW}\}$ and the other letters are equal to one of these, i.e., $l_i \in \{l_{k-1}, l_k\}$ for all $i \leq k-2$. This wind direction points precisely in the middle of the following two wind directions:

<ul>
	<li>wind direction $l_2\ldots l_k$,</li>
	<li>the first wind direction of at most $k-1$ letters you encounter when starting in $l_2\ldots l_k$ and move along the circle towards $l_1$.</li>
</ul>

For example, the wind direction SSSE points in the middle of SSE and S, because S is the first wind direction with at most 3 letters when moving from SSE towards S, as can also been seen in Figure F.1.

## 입력

The input consists of:

<ul>
	<li>One line with two strings $X$ and $Y$ ($1 \leq |X|, |Y| \leq 1000$), indicating the wind directions as described above.</li>
</ul>

## 출력

Output the smallest turn you have to make to go from direction $X$ to $Y$.

Your answer should have an absolute error of at most $10^{-6}$.

## 풀이
마지막 문자의 각도에서 시작해서 움직이는 각도를 절반씩 줄여가며 위로 갈지, 아래로 갈지 결정하는 문제였습니다. 지문 이해가 어려웠습니다.

``` c++
#include<bits/stdc++.h>
using namespace std;

typedef long double ld;

unordered_map<char, ld> dir = {
 {'N', 0},
 {'E', 90},
 {'S', 180},
 {'W', 270}
};

ld getDir(string s) {
    ld moveAng=90;
    ld cur = dir[s.back()];
    for(int i=s.length()-2;i>=0;i--) {
        int next = dir[s[i]];
        if(s[i]=='N' && cur>=270) next = 360;

moveAng/=2;
        if(next>cur) cur += moveAng;
        else cur -= moveAng;
    }
    return cur;
}

int main() {
 ios::sync_with_stdio(0); cin.tie(0);
 string x, y; cin >> x >> y;
 ld a = getDir(x), b = getDir(y);
 cout << fixed << setprecision(6) << min(max(a, b)-min(a, b), min(a, b)-max(a, b)+360);
}
```