Kralj i Kraljice


Submit solution

Points: 100 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type
Allowed languages
C++, Haskell, PyPy, Python

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 -6

Primjer izlaza

YES
Pojaš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 -2

Primjer izlaza

NO
Pojaš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 98

Primjer izlaza

NO
Pojaš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

There are no comments at the moment.