.campion
conectare | înregistrare | căutare
Pagina principală » Probleme » forum

ultima problemă
grupă: mică
sursă: OMI 2016
ultimul articol
autor: Prof. Radu Vişinescu
ultimul software
autor: Prof. Emanuela Cerchez
.campion
forum


Timp maxim de execuţie/test:
0.35 secunde
Memorie totala disponibilă/stivă:
16 MB/1 MB

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
filipb2001@yahoo.com
propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
surse trimise | ajutor