You are given M axis parallel right angled triangles ( one side on the x-axis and the other on y-axis ) with one vertex as origin. You are also provided with the co-ordinates of N candies in the plane. State for each triangle if there is atleast one candy which lies inside the triangle.Assume that no candy lies on the triangle.
First line of input contains t - the number of test cases.
For each test case, the first line contains two numbers N ( number of candies) and M (number of triangles). Then follow N lines each containing 2 space separated integer denoting the x and y co-ordinate of the candy. Next M lines contain 4 space separated integer x1,y1,x2 and y2 - the co-ordinates of 3 vertex of triangle hence are (0,0),(x1,y1) and (x2,y2).
0 <= N,M <= 100000
All co-ordinate values fit in a 32 bit signed variable.
Warning : Large Input Data.
For each test case, output M lines each containing a single character 'Y' or 'N'. If there is atleast one candy inside the corresponding triangle, output 'Y' ( without quotes ) else output 'N' (without quotes).
1 2 1 1 1 2 2 1 0 0 1
N
Migrated from old NTUJ.
CodeCraft 2010
| No. | Testdata Range | Score |
|---|