Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | tri3.in, tri3.out | Sursă | CEOI 2009 |
| Autor | Mihai Patrascu | Adăugată de |  Andrei-Bogdan Antonescu •andrei-alpha |
| Timp execuţie pe test | 0.675 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Tri3
Se dau K puncte cu coordonate numere întregi pozitive. De asemenea, se mai dau M triunghiuri, fiecare dintre ele având un vârf in origine iar celelalte doua vârfuri la coordonate numere întregi pozitive.
Determinaţi pentru fiecare triunghi daca are in interiorul sau cel puţin unul din cele K puncte date.
Niciunul dintre cele K puncte nu se găseşte pe o latura a oricărui triunghi.
Date de intrare
Prima linie a fişierului de intrare tri3.in va conţine K si M. Următoarele K linii conţin cate 2 numere întregi x si y, separate printr-un spaţiu, reprezentând coordonatele punctelor. Următoarele M linii conţin cate 4 numere întregi pozitive, separate printr-un spaţiu, (x1, y1) si (x2, y2), reprezentând celelalte 2 vârfuri ale triunghiului, exceptând pe cel din origine.
Date de ieşire
Fişierul de ieşire tri3.out conţine exact M linii. Linia k conţine caracterul Y daca al k-lea triunghi (in ordinea data in fişierul de intrare) conţine cel puţin un punct in interiorul sau, sau N in caz contrar.
Restricţii şi precizări
- 1 ≤ K, M ≤ 100 000
- 1 ≤ coordonatele celor K puncte ≤ 109
- 0 ≤ coordonatele vârfurilor triunghiurilor ≤ 109
- Triunghiurile nu sunt degenerate (toate au aria diferita de 0).
- In 50% din teste, toate triunghiurile au vârfurile in punctele cu coordonate x1 = 0 si y2 = 0. Acest lucru înseamnă ca doua din laturile triunghiului se găsesc pe axele de coordonate.
Exemplu
| tri3.in | tri3.out | Explicatie |
|---|---|---|
| 4 3 1 2 1 3 5 1 5 3 1 4 3 3 2 2 4 1 4 4 6 3 | Y N Y | 
|
| tri3.in | tri3.out | Explicatie |
|---|---|---|
| 4 2 1 2 1 3 5 1 4 3 0 2 1 0 0 3 5 0 | N Y | 
|
