303807: CF734D. Anton and Chess
Memory Limit:256 MB
Time Limit:4 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Anton and Chess
题意翻译
## **题目描述** Anton喜欢下棋与编程,所以他决定写一个国际象棋游戏。然而,他认为8x8的棋盘太简单了,因此这个棋盘是无限大的。 他的第一个任务是检查当前状态下是否被将军,他并不知道如何实现这点,因此向你求助。 棋盘上有一个白色方的王与n个黑色方的棋子,它们仅由车、象和后组成。当至少一个黑色方的棋子可以在一步内移动到白色方王所在的格子时被视为将军。 帮助Anton写一个程序,在给定所有棋子的位置时判定白色方的王是否被将军。 以下是各种棋子的移动方式: - 象可以斜着移动,格子不限。 - 车可以水平或垂直移动,格子不限。 - 后可以水平、垂直或斜着移动,格子不限。 - 所有的棋子不能越过已经占用的格子。 ## **输入输出格式** ### 输入格式: 第一行包含一个整数n(1<=n<=500 000),代表黑色方棋子的数量。 第二行包含两个整数x0和y0(-10^9<=x0,y0<=10^9),代表白色方王的坐标。 接下来的n行,每行包含一个字符和两个整数xi和yi(-10^9<=xi,yi<=10^9),字符'B'代表象,'R'代表车,'Q'代表后,xi和yi代表它们在棋盘上的坐标。题目确保所有的棋子不会出现在同样的位置。 ### 输出格式: 输出由一行组成:如果被将军,则输出"YES"(不带引号),否则输出"NO"(不带引号)。题目描述
Anton likes to play chess. Also, he likes to do programming. That is why he decided to write the program that plays chess. However, he finds the game on $ 8 $ to $ 8 $ board to too simple, he uses an infinite one instead. The first task he faced is to check whether the king is in check. Anton doesn't know how to implement this so he asks you to help. Consider that an infinite chess board contains one white king and the number of black pieces. There are only rooks, bishops and queens, as the other pieces are not supported yet. The white king is said to be in check if at least one black piece can reach the cell with the king in one move. Help Anton and write the program that for the given position determines whether the white king is in check. Remainder, on how do chess pieces move: - Bishop moves any number of cells diagonally, but it can't "leap" over the occupied cells. - Rook moves any number of cells horizontally or vertically, but it also can't "leap" over the occupied cells. - Queen is able to move any number of cells horizontally, vertically or diagonally, but it also can't "leap".输入输出格式
输入格式
The first line of the input contains a single integer $ n $ ( $ 1<=n<=500000 $ ) — the number of black pieces. The second line contains two integers $ x_{0} $ and $ y_{0} $ ( $ -10^{9}<=x_{0},y_{0}<=10^{9} $ ) — coordinates of the white king. Then follow $ n $ lines, each of them contains a character and two integers $ x_{i} $ and $ y_{i} $ ( $ -10^{9}<=x_{i},y_{i}<=10^{9} $ ) — type of the $ i $ -th piece and its position. Character 'B' stands for the bishop, 'R' for the rook and 'Q' for the queen. It's guaranteed that no two pieces occupy the same position.
输出格式
The only line of the output should contains "YES" (without quotes) if the white king is in check and "NO" (without quotes) otherwise.
输入输出样例
输入样例 #1
2
4 2
R 1 1
B 1 5
输出样例 #1
YES
输入样例 #2
2
4 2
R 3 3
B 1 5
输出样例 #2
NO