P16196 [ROIR 2014 Day 1] Majorhouse 市长府

在规划新城区 $M$ 时，决定让街道形成一个规整的矩形网格，也就是说，所有街道都分为两种：南北向和东西向。每条平行街道间隔一公里，每个街区正好是 $1$ 公里 $\times1$ 公里的方块。这样，整个道路系统就像一个均匀的格子。 每条路都允许双向通行。 但建成后发现，这样的规划并不总是方便。因为建大型工厂或公园时，单个街区不够用。于是市政![]()府决定给每个大型项目分配一个由若干相邻街区组成的矩形区域。遗憾的是，这些区域内的道路将全部封闭，禁止通行，但区域边界的道路仍可通行。两个区域相邻接触时，边界道路仍然开放，不会封闭。 当市长拿到这些大型项目区域分布图时，他想知道从市政![]()府大楼到他未来家的路线难不难走。市政![]()府位于新区中心，坐标是南北向的 $0$ 号街和东西向的 $0$ 号街的交叉口。市长还没决定最终住哪儿，他有 $k$ 个备选位置。每个位置在第 $x_i$ 条南北街和第 $y_i$ 条东西街的交叉口（$x>0$ 表示东边，$x0$ 表示北边，$y

第一行包含两个整数 $n$ 和 $k\ (0 \le n \le 100\,000,1 \le k \le 10)$，分别表示被划为大型项目的街区数量和市长家备选位置数量。 接下来 $n$ 行，每行四个整数 $u_1,v_1,u_2,v_2\ (-10^9 \le u_1 < u_2 \le 10^9,-10^9 \le v_1 < v_2 \le 10^9)$，表示被封闭的街区矩形两个对角的街道编号。 最后 $k$ 行，每行两个整数 $x_i$ 和 $y_i\ (|x_i| \le 10^9,|y_i| \le 10^9)$，且 $x_i \ne 0$ 或 $y_i \ne 0$，表示市长家的备选位置。 市政![]()府和所有备选位置都不在封闭街区内，但封闭街区之间可能重叠。

对于每个备选位置，按输入顺序输出是否存在不复杂路线。 若不存在，输出一行 `NO`。 若存在，第一行输出 `YES`；第二行输出转弯次数 $t\ (0 \le t \le 2)$；接下来 $t$ 行，每行三个整数 $x, y, d$，表示转弯的路口坐标和转弯方向（$d = -1$ 表示左转，$d = 1$ 表示右转）。转弯路口坐标不超过 $10^9$。若有多条最短不复杂路线，输出任意一条。

下面是第二个样例的示意图。  ### 评分 对于 $30$ 分的数据，坐标小于 $100$ 且 $n\le 50$。 对于 $60$ 分的数据，$n\le 50$。 翻译来源：GPT 4.1 mini。