[백준/BOJ] 20041 Escaping

문제 : 20041 Escaping

20041번: Escaping

도둑의 좌표가 주어지고 경찰의 좌표가 주어졌을 때

도둑이 영원히 도망칠 수 있는지 확인하는 문제이다.

기본적인 아이디어로는 도둑이 도망치는게 가능하다고 할때 굳이 지그재그로 갈 필요없이

위, 아래, 오른쪽, 왼쪽 중에서 한방향을 정해 쭉 달리면 된다는것을 알수 있고

이를 이용해 위, 아래, 오른쪽, 왼쪽 모두에 경찰이 존재할때만 도망치는것이 불가능함을 알수있다.

 

여기에서 현재 경찰이 있는 점이 어느 한 방향을 막을수 있는지 체크하기 위해서는

x축의 차이와 y축의 차이를 비교해서 작거나 같은쪽의 방향을 막는다고 생각하면 된다.

주의할점은 경찰이 (0,0)같이 여러 사분면에 걸쳐있을수 있으므로

else if가 아닌 if문으로 각각 처리해주어야 한다. 

---

Code

#include <bits/stdc++.h>
#define ll long long
using namespace std;
typedef pair<ll,ll> pll;
ll N, ans, x, y, chk[4]; // {up, down, left, right}
vector<pll> arr;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N;
    for (int i=0;i<N;i++){
        ll a, b;
        cin >> a >> b;
        arr.push_back({a,b});
    }
    cin >> x >> y;
    for (auto i:arr){
        ll a=i.first-x, b=i.second-y;
        if (a>=0 && b>=0){
            if (a>=b)
                chk[3]=1;
            if (b>=a)
                chk[0]=1;
        }
        if (a>=0 && b<=0){
            if (a>=abs(b))
                chk[3]=1;
            if (abs(b)>=a)
                chk[1]=1;
        }
        if (a<=0 && b<=0){
            if (abs(a)>=abs(b))
                chk[2]=1;
            if (abs(b)>=abs(a))
                chk[1]=1;
        }
        if (a<=0 && b>=0){
            if (abs(a)>=b)
                chk[2]=1;
            if (b>=abs(a))
                chk[0]=1;
        }
    }
    for (auto i:chk)
        ans+=i;
    cout << (ans==4 ? "NO" : "YES");
    return 0;
}