CEOI09TR - Tri

no tags 

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 ≤ 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 non-zero 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.
  • if (0, 0), (x1, y1) and (x2, y2) are 3 vertices of the query triangle and x1 < x2, then y1 > y2.

Example

Input 1:
4 3
1 2
1 3
5 1
5 3
1 4 3 3
2 2 4 1
4 4 6 3

Output 1:
Y
N
Y
Input 2:
4 2
1 2
1 3
5 1
4 3
0 2 1 0
0 3 5 0

Output 2:
N
Y

Explanation for Example 1

Explanation for example 1

Explanation for Example 2

Explanation for example 2

CEOI 2009 - Tîrgu Mureş, Romania


hide comments
[Rampage] Blue.Mary: 2022-12-02 09:48:04

@Simes
A very important constraint is not mentioned in problem statement:
if (0,0)(x1, y1)(x2,y2) are 3 vertices of the query triangle and x1 < x2, then y1 > y2.
[Simes]: constraint added.

@mihaell
The test case you mentioned in comment doesn't satisfy the above condition.

Last edit: 2022-12-02 22:38:06
Mihael: 2015-08-27 22:47:21

I found a test case for which my first AC submission gives the wrong output:

8 1
2 9
3 3
3 8
3 10
4 1
9 1
9 2
9 10
2 7 10 8

Bartek Dudek: 2012-06-03 11:39:09

Nice problem :)


Added by:Andrés Mejía-Posada
Date:2010-01-18
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS OBJC PERL6 SQLITE VB.NET
Resource:CEOI 2009 - Tîrgu Mureş, Romania