Locuințe
Limbajele de programare acceptate: Pascal, C și C++
Compilatoarele utilizate: Borland Pascal 7.0 și Borland C++ 3.1
Descrierea problemei
Elfii din Pădurea Aurie locuiau în căsuțe construite în vârfurile
copacilor. Ei au dorit să creeze o cărare dreaptă care să separe
căsuțele elfilor care poartă straie confecționate din materiale cu
nuanțe deschise de verde de căsuțele elfilor care poartă straie
confecționate din materiale cu nuanțe închise de verde.
Nimeni nu a reușit să își dea seama de ce au
luat această decizie, dar trebuie să încerce să creeze o astfel de
cărare.
Se cunosc coordonatele căsuțelor tuturor
elfilor și mai mulți elfi doresc să propună poziții ale potecii.
Dintre propuneri vor fi luate în considerare cele care respectă condiția amintită.
Evident, o potecă ce trece exact prin poziția unei căsuțe nu va fi acceptată.
Date de intrare
Fișierul de intrare INPUT.TXT conține pe prima linie numărul n al elfilor cu straie cu nuanțe deschise de verde.
Fiecare dintre următoarele n
linii conține câte două întregi, separate printr-un spațiu, care
reprezintă coordonatele căsuței unui elf îmbrăcat în straie de culoare
deschisă.
Următoarea linie a fișierului conține numărul m al elfilor cu straie cu nuanțe închise de verde.
Fiecare dintre următoarele m
linii conține câte două numere întregi, separate printr-un spațiu, care
reprezintă coordonatele căsuței unui elf îmbrăcat în straie de culoare
închisă.
Următoarea linie va conține numărul k al elfilor care doresc să propună amplasamente ale cărării.
Pe fiecare dintre următoarele k
linii se vor afla câte patru numere, separate prin câte un spațiu,
reprezentând coordonatele a două puncte distincte care vor determina
linia care descrie cărarea propusă de un elf.
Date de ieșire
Fișierul de ieșire OUTPUT.TXT trebuie să conțină k linii, fiecare corespunzând unei cărări propuse de un elf.
În cazul în care cărarea este acceptabilă, linia va conține mesajul DA, iar în cazul în care cărarea este inacceptabilă, linia va conține mesajul NU.
Mesajul de pe prima linie va corespunde primei
cărări propuse în fișierul de intrare, mesajul de pe a doua linie va
corespunde celei de-a doua cărări propuse și așa mai departe până la
mesajul de pe ultima linie care corespunde ultimei cărări propuse de
către elfi.
Restricții și precizări
nuumărul elfilor cu straie confecționate din materiale deschise la culoare este cuprins între 1 și 500;
numărul elfilor cu straie confecționate din materiale închise la culoare este cuprins între 1 și 500;
nu pot exista două căsuțe la aceleași coordonate;
toate coordonatele sunt numere întregi cuprinse între 0 și 1000.
Exemplu
INPUT.TXT
2
0 0
0 2
2
2 0
2 2
3
0 1 2 1
1 0 1 2
0 0 1 2
OUTPUT.TXT
NU
DA
NU
Timp de execuție: 2 secunde/test
|