SP5902 CEOI09TR - Tri

**Task** 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.) **Input** The first line of the input file 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. **Output** The output file 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. **Constraints** - 1 K,**M** - 1 K points - 0 - 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. **Sample input 1** 4 3 1 2 1 3 5 1 5 3 1 4 3 3 2 2 4 1 4 4 6 3 **Sample output 1** Y N Y **Explanation for sample 1**  **Sample input 2** 4 2 1 2 1 3 5 1 4 3 0 2 1 0 0 3 5 0 **Sample output 2** N Y **Explanation for sample 2** **** [**- - - - - -**](http://www.ceoi2009.ro) `

CEOI 2009 - Tîrgu Mureş, Romania`
                            

N/A

N/A