MINASTIRITH (상, p. 388)

문제#

어떻게 풀었나?#

핵심은 성벽인 원을 선으로 바꿔서 생각하는 것이다. 그러면 병사들이 성벽을 감시하는 구간을 선분으로 나타낼 수 있고, 이 문제는 다음과 같이 변형할 수 있다.

”긴 직선(성벽)을 여러 개의 선분을 겹쳐서 커버하고자 할 때, 직선을 완전히 커버할 수 있는 최소 선분 개수를 구하시오.”

1) 병사가 감시하는 영역 → 직선의 구간으로 표현하기#

병사들이 서있는 좌표를 $(x,y)$라 할 때, 원점부터 $(x,y)$까지의 방향각을 $\theta$라 하자. $\theta$는 다음과 같이 나타낼 수 있다.

$\theta = atan2(y,x)$

그런데, $atan2()$의 치역은 폐구간 $[-\pi,\pi]$에 해당한다. 우리는 이를 $[0,2\pi]$로 바꾸기 위해 $atan2()$값이 음수이면, $2\pi$를 더해주면 된다. 이를 C++에선 간단히 아래와 같이 표현할 수 있다. 기하 문제에서는 공식이나 다름없다.

$\theta = fmod(atan2(y, x) + 2\pi, 2\pi)$

이제 병사가 감시하는 성벽의 끝단 좌표를 구하면 된다. 이는 $\theta$로 부터 $\pm \delta$로 표현할 수 있고, $\delta$로 표현되는 각을 이루는 삼각형이 이등변삼각형 이므로, $\delta$는 다음과 같이 구할 수 있다. (※ r=병사들이 감시 반지름, R=성벽 반지름)

$\delta = 2\times asin(\frac{\frac{r}{2}}{R}) = 2\times asin(\frac{r}{2R})$

그리고 병사가 감시하는 영역은 다음과 같이 표현할 수 있다.

$[\theta-\delta,\theta+\delta]$

여기서 주의해야 할 점은, $\theta$값이 $[0,2\pi]$값을 가지므로, 여기에 $\delta$값을 빼고 더하는 경우 $0$보다 작고 $2\pi$보다 큰 값이 나오므로 이를 잘 처리해야하는데, 나는 $2\pi$를 넘어가는 구간값을 갖는 경우 모두 $2\pi$를 빼서 구간의 범위를 통일화 했다. 이렇게 하면 $[\theta-\delta,\theta+\delta]$는 구간 $[-\pi,2\pi)$의 값을 갖게 된다.

2) 직선을 여러개의 선분으로 덮는 그리디 방식#

일단 최초의 선분 1개를 선택하면, 이 직선을 덮는 최소 개수의 선분들은 정해진 것이나 다름이 없다. 왜냐하면, 선택된 선분과 겹치는 모든 선분들 중에서 가장 긴 선분을 고르고, 이 행위를 계속 반복해 나가면, 그것이 최소 개수의 선분들을 선택하는 방법이 되기 때문이다.

그러면 최초의 선분 1개를 어떻게 택해야 할까? 모든 선분을 다 고려해야할까? 사실 그렇게 해도 시간안으로 들어온다. 하지만 잘 생각해보면 직선위의 점 0을 커버하는 선분들만 고려해보면 된다. 왜냐하면, 병사가 감시하는 성벽의 범위 $[\theta-\delta,\theta+\delta]$는 구간 $[-\pi,2\pi)$의 값을 갖도록 만들어놨으므로, 0을 커버하는 선분(병사)은 반드시 하나만 존재하기 때문이다.

3) r≥2R인 예외사항 고려#

$r \ge 2R$인 경우 병사 1명만으로도 성벽을 모두 감시할 수 있는데, 이런 경우 위에서 언급한 $\theta, \delta$가 정의 될 수 없으므로 따로 처리해줘야 한다.

※ θ는 왜 atan(y/x)로는 나타낼 수 없을까?#

$atan(y/x)$는 치역이 $[-\pi/2,\pi/2]$에 해당한다. 이는 치역만 봐도 4사분면중 2개의 사분면만 표현하는 문제가 있고, 정의역을 보면 애초에 인자로 들어가는 값이 “기울기”이다. → 즉, $atan(y/x)$는 “기울기만” 계산한다.

따라서 원점부터 $(x,y)$까지의 방향각($\theta$)을 구하려면 $atan2(y,x)$를 사용해야 한다.

정답 코드#

#include <bits/stdc++.h>
using namespace std;
using pdd = pair<double,double>;
const int INF = 0x3f3f3f3f;
inline double PI() {
    static const double value = acos(-1);
    return value;
}
inline double GetTheta(double x, double y) {
    return fmod(atan2(y, x) + 2 * PI(), 2 * PI());
}

vector<pdd> v;
int CountCover(int si, double final_dest) {
    if(final_dest <= v[si].second) return 1;

    double mx=-INF;
    int mxi = -1;
    for(int i=si+1; i<v.size(); i++) {
        if(v[i].first <= v[si].second) {
            if(mx < v[i].second) {
                mx = v[i].second;
                mxi = i;
            }
        }
        else break;
    }

    if(mxi == -1) return INF;
    else return CountCover(mxi, final_dest)+1;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int tc; cin >> tc;
    while (tc--) {
        v.clear();
        int n; cin >> n;
        double x, y, r, mx_r = 0;
        for (int i = 0; i < n; i++) {
            cin >> x >> y >> r;
            mx_r = max(r, mx_r);

            double theta = GetTheta(x,y);
            double delta = 2*asin(r/16.0);
            v.emplace_back(theta-delta, theta+delta);
        }

        if(mx_r>=16.0) {
            puts("1");
            continue;
        }

        for(int i=0; i<v.size(); i++) {
            if(v[i].second>=2*PI()) {
                v[i].first -= 2*PI();
                v[i].second -= 2*PI();
            }
        }

        sort(v.begin(), v.end());

        int ans = INF;
        for(int i=0; i<v.size(); i++) {
            if(v[i].first<=0) {
                ans = min(ans, CountCover(i, 2*PI() + v[i].first));
            }
        }
        if(ans==INF) puts("IMPOSSIBLE");
        else printf("%d\n", ans);
    }
    return 0;
}

Comment#

이 문제가 인생 첫 기하문제였기 때문에 알고리즘적으로 기하문제를 푸는 지식이 전무하여 내가 알고 있는 수학적 지식을 모두 동원하여 풀기 시작했다. 두 원이 겹치는 경우를 따지는 방법, 원 내부에 (x,y)가 존재하는것을 판별하는 방법, 두 원이 겹칠 때 생기는 두 점이 성벽 안과 밖에 생기는 경우를 따지는 방법 등등.. 이런 것들을 모두 구현했지만, 역시 계속 WA를 받았다.

그 이후 책을 조금씩 참고하면서 풀었고, 겨우 AC를 받을 수 있었다.

여기서 꼭 알아둬야 할 것은 다음과 같다.

1) (0,0)→(x,y) 방향각 표현법#