Dupa ce Imperiul Roman s-a dezvoltat suficient, a aparut
problema construirii unui forum. Acest lucru nu era deloc unul simplu,
in special in conditiile in care Roma era un oras foarte populat. Putem
presupune ca in oras erau N case, fiecare
situata la un punct in plan de coordonate intregi. Forumul trebuia construit
astfel incat sa indeplineasca urmatoarele conditii:
sa fie de forma circulara
construirea lui sa nu implice daramarea vreunei case (oricare dintre
cele N case sa nu fie in interiorul sau
pe marginile forumului)
centrul Imperiului Roman, considerat punctul de coordonate (0,0),
sa fie pe marginile forumului
In urma anuntului facut de imparat, M arhitecti
romani au venit fiecare cu o posibila propunere pentru amplasarea forumului.
Prin amplasare se intelege o pereche de numere (x
y) astfel incat centrul forumului sa coincida cu punctul (x
y).
Cerinta
Dandu-se cele M propuneri ale arhitectilor sa se decida care dintre ele
sunt valide. O propunere este valida daca este posibila construirea unui
forum circular in pozitia precizata, astfel incat centrul imperiului sa
fie pe circumferinta si constructia forumului sa nu implice daramarea
vreunei case.
Date de intrare
Fisierul de intrare forum.in contine pe prima
linie doua numere naturale N si M,
reprezentând numarul de case si respectiv numarul de amplasari propuse.
Fiecare dintre urmatoarele N linii contine
cate o pereche de numere intregi, semnificand pozitia unei case romane.
Fiecare dintre urmatoarele M linii contine
tot o pereche de numere intregi, descriind o posibila locatie pentru forum.
Date de iesire
Fisierul de iesire forum.out va contine M
linii, pe fiecare fiind scris mesajul DA
sau NU, in functie de validitatea propunerii
corespunzatoare din fisierul de intrare.
Restrictii
1 <= N, M <= 100000
Toate coordonatele din fisierul de intrare sunt numere intregi nenule
in intervalul [-32000, +32000]
Pot exista doua case, doua amplasari sau o casa si o amplasare in
acelasi punct
Exemplu
forum.in
forum.out
3 2
2 6
4 1
-2 3
1 2
4 3
DA
NU
Filip Cristian Buruiana
stud. Facultatea de Automatica si
Calculatoare, Universitatea Politehnica, Bucuresti