codeforces 734 (思维暴力)

71 阅读 0 评论 47 点赞

我是靠谱客的博主感性康乃馨，最近开发中收集的这篇文章主要介绍codeforces 734 (思维暴力)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

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".

Input

The first line of the input contains a single integer n (1 ≤ n ≤ 500 000) — the number of black pieces.

The second line contains two integers x0 and y0 ( - 109 ≤ x0, y0 ≤ 109) — coordinates of the white king.

Then follow n lines, each of them contains a character and two integers xi and yi ( - 109 ≤ xi, yi ≤ 109) — 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.

Output

The only line of the output should contains "YES" (without quotes) if the white king is in check and "NO" (without quotes) otherwise.

Examples

input
2
4 2
R 1 1
B 1 5

output
YES

input
2
4 2
R 3 3
B 1 5

output
NO

Note

Picture for the first sample:

$\text{[math]}$ White king is in check, because the black bishop can reach the cell with the white king in one move. The answer is " YES".

Picture for the second sample:

$\text{[math]}$ Here bishop can't reach the cell with the white king, because his path is blocked by the rook, and the bishop cant "leap" over it. Rook can't reach the white king, because it can't move diagonally. Hence, the king is not in check and the answer is " NO".

三种棋子走向：

棋子一，沿对角线走

棋子二：水平走或者竖直走

棋子三：沿对角线，水平，或者竖直走

棋子一次可以走任意长度，但是如果棋子和king之间有棋子，就不能走，最后攻击king所在位置

算出每个棋子到king 的距离，然后从小到大排列，遍历所有点，离king 的八个方向最近的棋子能不能攻击king

代码：

#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct Node
{
char ch[10];
int x,y;
__int64 d;
}a[500010];
bool cmp(Node a,Node b)
{
return a.d<b.d;
}
int main()
{
int n;
__int64 x0,y0;
int vis[10];
scanf("%d",&n);
scanf("%I64d%I64d",&x0,&y0);
memset(vis,0,sizeof(vis));
for(int i=0;i<n;i++)
{
scanf("%s%d%d",a[i].ch,&a[i].x,&a[i].y);
__int64 xx=a[i].x;
__int64 yy=a[i].y;
a[i].d=(xx-x0)*(xx-x0)+(yy-y0)*(yy-y0);
}
sort(a,a+n,cmp);
int flag=0;
for(int i=0;i<n;i++)
{
if(flag==1)
break;
if(a[i].x==x0)
{
if(a[i].y>y0&&vis[1]==0)
{
vis[1]=1;
if(a[i].ch[0]=='R'||a[i].ch[0]=='Q')
flag=1;
}
else if(a[i].y<y0&&vis[2]==0)
{
vis[2]=1;
if(a[i].ch[0]=='R'||a[i].ch[0]=='Q')
flag=1;
}
}
else if(a[i].y==y0)
{
if(a[i].x<x0&&!vis[3])
{
vis[3]=1;
if(a[i].ch[0]=='R'||a[i].ch[0]=='Q')
flag=1;
}
else if(a[i].x>x0&&!vis[4])
{
vis[4]=1;
if(a[i].ch[0]=='R'||a[i].ch[0]=='Q')
flag=1;
}
}
else if(abs(a[i].x-x0)==abs(a[i].y-y0))
{
if(a[i].x>x0&&a[i].y>y0&&!vis[5])
{
vis[5]=1;
if(a[i].ch[0]=='B'||a[i].ch[0]=='Q')
flag=1;
}
else if(a[i].x>x0&&a[i].y<y0&&!vis[6])
{
vis[6]=1;
if(a[i].ch[0]=='B'||a[i].ch[0]=='Q')
flag=1;
}
else if(a[i].x<x0&&a[i].y>y0&&!vis[7])
{
vis[7]=1;
if(a[i].ch[0]=='B'||a[i].ch[0]=='Q')
flag=1;
}
else if(a[i].x<x0&&a[i].y<y0&&!vis[8])
{
vis[8]=1;
if(a[i].ch[0]=='B'||a[i].ch[0]=='Q')
flag=1;
}
}
}
if(flag==1)
printf("YESn");
else
printf("NOn");
return 0;
}