Fişierul intrare/ieşire: | poligon.in, poligon.out | Sursă | ad-hoc |
Autor | clasica | Adăugată de | |
Timp execuţie pe test | 0.2 sec | Limită de memorie | 4096 kbytes |
Scorul tău | N/A | Dificultate |
Poligon
Se dă un poligon cu N vârfuri şi alte K puncte-interogare în plan. Pentru fiecare dintre cele K puncte, să se spună dacă el aparţine sau nu poligonului.
Punctele care sunt pe conturul poligonului sunt considerate ca aparţinând poligonului. Punctele-interogare sunt distincte de vârfurile poligonului. Poligonul este simplu, adică nu se autointersectează.
Date de intrare
Fişierul de intrare poligon.in conţine pe prima linie numerele N şi K. Pe următoarele N linii sunt date, în ordine, vârfurile poligonului prin coordonatele x şi y. Pe următoarele K linii sunt date cele K puncte-interogare prin coordonatele x şi y. Toate coordonatele sunt numere reale cu trei zecimale.
Date de ieşire
În fişierul de ieşire poligon.out se vor scrie K linii. Pe fiecare linie se va scrie DA sau NU după cum punctul-interogare corespunzător aparţine sau nu poligonului.
Restricţii
- 1 ≤ N ≤ 500
- 1 ≤ K ≤ 10
- coordonatele sunt cuprinse între 1 şi 1.000.000.
Exemplu
poligon.in | poligon.out |
---|---|
7 2 5.000 7.000 6.000 2.000 11.000 4.000 7.000 6.000 8.000 9.000 3.000 10.000 2.000 5.000 4.000 5.000 6.000 8.000 | NU DA |