== include(page="template/taskheader" task_id="tri3") ==
Se dau $K$ puncte cu coordonate numere intregi pozitive. De asemenea, se mai dau $M$ triunghiuri, fiecare dintre ele avand un varf in origine iar celelalte doua varfuri la coordonate numere intregi pozitive.
Determinati pentru fiecare triunghi daca are in interiorul sau cel putin unul din cele $K$ puncte date.
Niciunul dintre cele $K$ puncte nu se gaseste pe o latura a oricarui triunghi.
Se dau $K$ puncte cu coordonate numere întregi pozitive. De asemenea, se mai dau $M$ triunghiuri, fiecare dintre ele având un vârf în origine iar celelalte două vârfuri la coordonate numere întregi pozitive.
Determinaţi pentru fiecare triunghi dacă are în interiorul său cel puţin unul din cele $K$ puncte date.
Niciunul dintre cele $K$ puncte nu se găseşte pe o latură a oricărui triunghi.
h2. Date de intrare
Prima linie a fisierului de intrare $tri3.in$ va contine $K$ si $M$. Urmatoarele $K$ linii contin cate $2$ numere intregi $x$ si $y$, separate printr-un spatiu, reprezentand coordonatele punctelor. Urmatoarele $M$ linii contin cate $4$ numere intregi pozitive, separate printr-un spatiu, $(x1,y1)$ si $(x2,y2)$, reprezentand celelalte $2$ varfuri ale triunghiului, exceptand pe cel din origine.
Prima linie a fişierului de intrare $tri3.in$ va conţine $K$ şi $M$. Următoarele $K$ linii conţin câte $2$ numere întregi $x$ şi $y$, separate printr-un spaţiu, reprezentând coordonatele punctelor. Următoarele $M$ linii conţin câte $4$ numere întregi pozitive, separate printr-un spaţiu, $(x{~1~}, y{~1~})$ şi $(x{~2~}, y{~2~})$, reprezentând celelalte $2$ vârfuri ale triunghiului, exceptând pe cel din origine.
h2. Date de ieşire
Fisierul de iesire $tri3.out$ contine exact $M$ linii. Linia $k$ contine caracterul $Y$ daca al $k$-lea triunghi (in ordinea data in fisierul de intrare) contine cel putin un punct in interiorul sau, sau $N$ in caz contrar.
Fişierul de ieşire $tri3.out$ conţine exact $M$ linii. Linia $k$ conţine caracterul $Y$ dacă al $k$-lea triunghi (în ordinea dată în fişierul de intrare) conţine cel puţin un punct în interiorul său, sau $N$ în caz contrar.
h2. Restricţii şi precizări
* $1$ ≤ $K,M$ ≤ $100.000$
* $1$ ≤ coordonatele celor $K$ puncte ≤ $109$
* $0$ ≤ coordonatele varfurilor triunghiurilor ≤ $109$
* Triunghiurile nu sunt degenerate (toate au aria diferita de $0$).
* In $50%$ din teste, toate triunghiurile au varfurile in punctele cu coordonate $x1 = 0$ si $y2 = 0$. Acest lucru inseamna ca doua din laturile triunghiului se gasesc pe axele de coordonate.
* $1 ≤ K, M ≤ 100 000$
* $1 ≤$ coordonatele celor $K$ puncte $≤ 10^9^$
* $0 ≤$ coordonatele vârfurilor triunghiurilor ≤ $10^9^$
* Triunghiurile nu sunt degenerate (toate au aria diferită de $0$).
* În $50%$ din teste, toate triunghiurile au vârfurile în punctele cu coordonate $x{~1~} = 0$ şi $y{~2~} = 0$. Acest lucru înseamnă că două din laturile triunghiului se găsesc pe axele de coordonate.
h2. Exemplu
table(example). |_. tri3.in |_. tri3.out |_. Explicatie |
table(example). |_. tri3.in |_. tri3.out |_. Explicaţie |
| 4 3
1 2
1 3
