Kralj i Kraljice
Trgovac Mihael u svojoj ponudi ima novu šahovsku ploču koja je beskonačno velika i figure se na njoj same pomiču. Tu ploču možete zamisliti kao koordinatni sustav gdje figure mogu imati i negativne koordinate. Dok je putovao svijetom figure su mu se u torbi ispomicale i završile u sljedećoj situaciji. Sve bijele figure osim kralja su izgubljene, a sve crne figure (čak i kralj) su promovirane u \(m\) kraljica. Bijeli je na potezu i Mihaela zanima može li ga pomaknuti tako da ga niti jedna kraljica ne napada? Dodatno, bijeli kralj ne smije jesti crne kraljice!
Kraljice napadaju sva polja vodoravno, okomito i u obje dijagonale. Kralj se smije pomaknuti u svih osam smjerova za jedno polje, što znači ako se kralj nalazi na \((x, y)\), onda smije otići na \((x + 1, y)\), \((x - 1, y)\), \((x, y + 1)\), \((x, y - 1)\), \((x + 1, y + 1)\), \((x + 1, y - 1)\), \((x - 1, y + 1)\) i \((x - 1, y - 1)\).
Ulaz
U prvom retku se nalaze tri broja \(x\), \(y\) i \(m\) \((-10^9 \leq x, y \leq 10^9, 0 \leq m \leq 10^5)\).
Uređeni par \((x, y)\) je pozicija kralja na šahovskoj ploči, a \(m\) je broj kraljica.
U svakom od sljedećih \(m\) redaka se nalaze dva broja \(x_i\) i \(y_i\) (-10^9 \leq x_i, y_i \leq 10^9)\(, pozicija \)i~-te kraljice na ploči.
Izlaz
U jedini redak ispišite "YES" ukoliko kralj može napraviti validan potez, a u suprotnom ispišite "NO".
U \(50%\) testnih primjera će za sve figure vrijediti \(-1000 \leq x_i, y_i \leq 1000\).
Primjer ulaza
-8 -8 3
-9 -9
-7 -10
-6 -6Primjer izlaza
YESPojašnjenje
Stanje ploče za prvi primjer je
....Q
Q....
..K..
.Q...
.....i kralj se ne može pomaknuti desno.
Primjer ulaza
0 0 2
1 1
-1 -2Primjer izlaza
NOPojašnjenje
Stanje ploče za drugi primjer je
.....
...Q.
..K..
Q....
.....i kralj se ne može nigdje pomaknuti tako da ga ne napada kraljica.
Kad bi kralj smio jesti kraljice, odgovor bi bio "YES", ali to nije dopušteno.
Primjer ulaza
100 100 4
102 101
99 102
98 99
101 98Primjer izlaza
NOPojašnjenje
Stanje zadnje ploče je
...Q.
Q....
..K..
....Q
.Q...i kralja ne napada niti jedna kraljica.
Kralj bi bio siguran da ostane na mjestu, no on se mora pomaknuti i zato je odgovor "NO".
Comments