== include(page="template/taskheader" task_id="tri3") ==
You are given K points with positive integer coordinates. You are also given M triangles, each
of them having one vertex in the origin and the other 2 vertices with non-negative integer
coordinates.
You are asked to determine for each triangle whether it has at least one of the K given points
inside. (None of the K points are on any edge of any triangle.)
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
The first line of the input file $tri3.in$ will contain $K$ and $M$. The following $K$ lines will
contain 2 positive integers x y separated by one space that represent the coordinates of
each point. The next M lines have 4 non-negative integers separated by one space, (x1,y1)
and (x2, y2), that represent the other 2 vertices of each triangle, except the origin.
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
The output file $tri3.out$ should contain exactly M lines. The k-th line should contain the
character Y if the k-th triangle (in the order of the input file) contains at least one point
inside it, or N otherwise.
h2. Restricţii
* $1 ≤ K,M ≤ 100.000$
* $1 ≤ each coordinate of the $K$ points ≤ 109$
* $0 ≤ each coordinate of the triangle vertices ≤ 109$
* $Triangles are not degenerate (they all have nonzero area).$
* $In 50% of the test cases, all triangles have vertices with coordinates x1=0 and y2=0. That is, one edge of the triangle is on the x-axis, and another is on the y-axis.$
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 $≤ 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
