프로그램 명: ceoi_tri
제한시간: 2 초
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 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.
출력
The output 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 ) 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 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.
입출력 예
입력
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
입력
4 2
1 2
1 3
5 1
4 3
0 2 1 0
0 3 5 0
출력
N
Y
출처:ceoi/2009/
스포일러
[질/답]
[제출 현황]
[푼 후(0)]