P16196 [ROIR 2014 Day 1] Majorhouse City Hall

When planning the new district $M$, it was decided that the streets should form a regular rectangular grid. That is, all streets are of two types: north-south and east-west. Any two parallel streets are $1$ kilometer apart, and each block is exactly a $1$ km $\times 1$ km square. Thus, the whole road system looks like a uniform grid. All roads allow traffic in both directions. However, after construction, it turned out that this plan is not always convenient, because when building large factories or parks, a single block is not enough. Therefore, the city hall decided to allocate each large project a rectangular area consisting of several adjacent blocks. Unfortunately, all roads inside such an area will be closed and impassable, while the roads on the boundary of the area are still passable. If two areas touch each other, the boundary roads are still open and will not be closed. When the mayor received the map of these large project areas, he wanted to know whether it would be difficult to travel from the city hall building to his future home. The city hall is located at the center of the new district, at the intersection of north-south street $0$ and east-west street $0$. The mayor has not decided where to live yet, and he has $k$ candidate locations. Each location is at the intersection of north-south street $x_i$ and east-west street $y_i$ ($x>0$ means east, $x0$ means north, $y

The first line contains two integers $n$ and $k\ (0 \le n \le 100\,000,1 \le k \le 10)$, representing the number of blocks assigned to large projects and the number of candidate home locations. The next $n$ lines each contain four integers $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)$, describing two opposite corners of a closed rectangular area in terms of street indices. The last $k$ lines each contain two integers $x_i$ and $y_i\ (|x_i| \le 10^9,|y_i| \le 10^9)$, with $x_i \ne 0$ or $y_i \ne 0$, representing a candidate home location. The city hall and all candidate locations are not inside any closed area, but closed areas may overlap.

For each candidate location, output whether a not-complicated route exists, in the input order. If it does not exist, output one line `NO`. If it exists, output `YES` on the first line; on the second line output the number of turns $t\ (0 \le t \le 2)$; then output $t$ lines, each containing three integers $x, y, d$, describing the intersection coordinates where a turn occurs and the turning direction ($d = -1$ means a left turn, $d = 1$ means a right turn). The coordinates of turning intersections do not exceed $10^9$. If there are multiple shortest not-complicated routes, output any one.

The following is an illustration of the second sample.  ### Scoring For the $30$-point testdata, coordinates are less than $100$ and $n \le 50$. For the $60$-point testdata, $n \le 50$. Translation source: GPT 4.1 mini. Translated by ChatGPT 5