Tri-ceoi
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.) Constraints
• 1 ≤ K,M ≤ 100 000
• 1 ≤ each coordinate of the K points ≤ 10^9
• 0 ≤ each coordinate of the triangle vertices ≤ 10^9
• Triangles are not degenerate (they all have nonzero area).
InputThe first line of the input 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.
OutputThe output file tri.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.
Input
Output
4 3
1 2
1 3
5 1
5 3
1 4 3 3
2 2 4 1
4 4 6 3 Output
Y
N
YExplanation
Image: dsadsa
Input
Output
4 2
1 2
1 3
5 1
4 3
0 2 1 0
0 3 5 0 Output
N
Y Explanation
Image: dsadsaa
Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.