2173: 孤独的骑士
内存限制：512 MB
时间限制：4 S
标准输入输出
题目类型：传统
评测方式：文本比较
上传者：
提交：1
通过：1
题目描述
给定一个无限的国际象棋棋盘，用整数坐标表示方格位置。
现有一个白色骑士，位于方格(xs,ys)处，想到达方格(xt,yt)。
同时，棋盘上存在 n 个黑色的车，保持不动。
白色骑士可以进行多次移动，但无法停留在被车攻击或占据的方格上。
请判断白色骑士能否到达目标方格。
注意：
骑士移动规则：横向移动两格纵向移动一格 或者 纵向移动一格横向移动两格，如左图。
车移动规则：可到达所在行或所在列任意方格，如右图。
现有一个白色骑士，位于方格(xs,ys)处，想到达方格(xt,yt)。
同时，棋盘上存在 n 个黑色的车，保持不动。
白色骑士可以进行多次移动，但无法停留在被车攻击或占据的方格上。
请判断白色骑士能否到达目标方格。
注意：
骑士移动规则：横向移动两格纵向移动一格 或者 纵向移动一格横向移动两格，如左图。
车移动规则：可到达所在行或所在列任意方格，如右图。
输入格式
第一行为两个正整数 n 和 q，分别表示黑色车的数量和询问次数，1≤n,q≤1000。
接下来 n 行，每行两个整数 X[i], Y[i]，表示第 i 个车的坐标。
接下来 q 行，每行四个整数 xs, ys, xt, yt，表示本次询问骑士能否从起点 (xs,ys) 到达 (xt,yt)。
所有坐标绝对值不超过 109，骑士的初始和终止方格不会被车占据或者攻击。
接下来 n 行，每行两个整数 X[i], Y[i]，表示第 i 个车的坐标。
接下来 q 行，每行四个整数 xs, ys, xt, yt，表示本次询问骑士能否从起点 (xs,ys) 到达 (xt,yt)。
所有坐标绝对值不超过 109，骑士的初始和终止方格不会被车占据或者攻击。
输出格式
对于每组询问，如果可以到达则输出 1，否则输出 0。
输入样例 复制
样例1：
6 6
10 14
1 0
0 1
4 9
9 13
5 9
2 2 3 4
2 2 2 4
2 2 6 4
2 2 2 10
7 11 6 2
6 2 8 12
样例2：
8 10
0 0
1 1
5 5
8 8
11 11
14 14
18 18
19 19
17 10 13 9
15 15 15 9
7 3 17 4
15 15 12 3
9 17 3 3
4 4 9 4
12 12 2 6
10 15 6 6
15 17 4 16
-1000000000 -999999999 15 7输出样例 复制
样例1：
1
0
0
1
0
1
样例2：
1
0
0
0
0
0
0
0
0
0数据范围与提示
来源：2023 PACNW