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

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.)

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.

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.

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.

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

Cum se trimit solutii?