20041번 - Escaping 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 512 MB | 883 | 411 | 331 | 47.353% |
문제
무한 정수 좌표 평면 위 한 격자 점에 있는 도둑 잡기 게임을 해 보자. 이 도둑을 잡기 위해 N명의 경찰이 도둑이 없는 N개의 다른 격자 점에 배치되어 있다. 도둑 한 명과 N명 경찰들은 서로 한번씩 번갈아 가면서 움직인다. 도둑이 먼저 시작한다. 경찰 차례일 때는 N 명의 경찰 모두가 동시에 움직인다. 경찰과 도둑은 상하좌우 인접한 네 개의 격자 점 중 하나로 이동할 수 있다. 단, 경찰은 그대로 머물러 있을 수 있지만 도둑은 자신의 차례가 오면 반드시 이웃 격자 점으로 이동해야 한다. 이때 경찰과 도둑이 같은 격자 점에서 만나면 도둑은 잡힌 것이 되고 게임은 끝이 난다. 이 게임에서 경찰과 도둑은 최선을 다한다. 즉, 도둑은 최대한 잡히지 않으려는 전략을, 경찰은 최대한 빨리 잡으려는 전략을 쓴다.
입력으로 주어진 초기 위치에서 경찰이 어떤 전략을 사용하더라도 도둑이 경찰에 의해 잡히지 않고 영원히 도망 다닐 수 있다면, 그 초기 조건은 도둑이 “탈출 가능한” 조건이라고 부른다. 여러분은 초기 조건, 즉 한 명의 도둑과 N 명의 경찰의 처음 위치를 보고 도둑이 탈출 가능한지 판단해야 한다.
예를 들어, 다음 아래 왼쪽 그림과 같은 초기 조건에서 도둑이 북쪽 또는 남쪽 방향으로만 움직인다면 경찰은 도둑을 영원히 잡을 수 없다. 그러나 아래 오른쪽 그림과 같은 조건이라면 도둑이 어떻게 도망을 가더라도 최선을 다하는 경찰에 의해서 결국은 잡히게 된다.
입력
첫 번째 줄에는 경찰의 수 N이 주어진다. 단, 1 ≤ N ≤ 500,000이다. 그 다음 N 개의 줄에는 각 경찰의 초기 위치의 좌표 (xi, yi)가 공백을 사이에 두고 주어진다. 다음 줄에는 도둑의 초기 위치의 좌표 (sx, sy)가 공백을 사이에 두고 주어진다. 도둑과 경찰의 좌표는 모두 다른 격자 점으로 주어지며, 정수 xi, yi, sx, sy의 범위는 −109 ≤ xi, yi, sx, sy ≤ 109이다.
출력
주어진 초기 조건에서 도둑이 무한히 도망갈 수 있다면, 즉, 초기 조건이 탈출 가능한 조건이라면, YES, 탈출 가능하지 않다면 NO 를 출력한다.
예제 입력 1
2 1 3 5 3 3 3
예제 출력 1
YES
예제 입력 2
2 1 5 5 1 3 3
예제 출력 2
NO
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호