[Solution] Ela and Crickets Codeforces Solution

C. Ela and Crickets

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

The problem, which involves a non-standard chess pieces type that is described below, reads: given 

3$3$ white crickets on a 𝑛⋅𝑛$n\cdot n$ board, arranged in an "L" shape next to each other, there are no other pieces on the board. Ela wants to know with a finite number of moves, can she put any white cricket on the square on row 𝑥$x$, column 𝑦$y$?

An "L"-shape piece arrangement can only be one of the below:

For simplicity, we describe the rules for crickets on the board where only three white crickets are. It can move horizontally, vertically, or diagonally, but only to a square in some direction that is immediately after another cricket piece (so that it must jump over it). If the square immediately behind the piece is unoccupied, the cricket will occupy the square. Otherwise (when the square is occupied by another cricket, or does not exist), the cricket isn't allowed to make such a move.

See an example of valid crickets' moves on the pictures in the Note section.

Input

Each test contains multiple test cases. The first line contains the number of test cases 𝑡$t$ (1≤𝑡≤104$1\le t\le {10}^4$). The description of the test cases follows.

The first line of each test case contains 𝑛$n$ (4≤𝑛≤105$4\le n\le {10}^5$) — denotes the size of the chessboard.

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

The second line of each test case contains 6 numbers: 𝑟1$r_1$, 𝑐1$c_1$, 𝑟2$r_2$, 𝑐2$c_2$, 𝑟3$r_3$, 𝑐3$c_3$ (1≤𝑟1,𝑐1,𝑟2,𝑐2,𝑟3,𝑐3≤𝑛$1\le r_1,c_1,r_2,c_2,r_3,c_3\le n$) — coordinates of the crickets. The input ensures that the three crickets are arranged in an "L" shape that the legend stated.

The third line of each test case contains 2 numbers: 𝑥$x$, 𝑦$y$ (1≤𝑥,𝑦≤𝑛$1\le x,y\le n$) — coordinates of the target square.

Output

For each test case, print "YES" or "NO" to denotes whether Ela can put a cricket on the target square.