삼각형
시간 제한1초메모리 제한128 MB
원점을 한 꼭짓점으로 하는 M개의 삼각형 각각에 대해 K개의 점 중 삼각형 내부(경계 제외)에 있는 점이 있는지 대량으로 판별하는 문제입니다.
문제
좌표가 모두 양의 정수인 점 K개와 삼각형 M개가 주어진다. 각 삼각형은 한 꼭짓점이 원점 (0, 0)이며, 나머지 두 꼭짓점의 좌표는 0 이상의 정수이다.
각 삼각형에 대해, 주어진 K개의 점 중 적어도 하나가 그 삼각형의 내부(경계를 제외한 순수한 내부)에 들어 있는지 판별하여라. 삼각형의 변이나 꼭짓점 위에 놓인 점은 경계에 있는 것으로 보아 내부에 있다고 하지 않는다.
입력
첫째 줄에 두 정수 K와 M이 주어진다.
다음 K개의 줄에는 각 점의 x좌표와 y좌표가 공백으로 구분되어 주어진다.
다음 M개의 줄에는 네 정수 x1 y1 x2 y2가 주어지며, 하나의 삼각형을 나타낸다. (x1, y1)과 (x2, y2)는 원점이 아닌 두 꼭짓점의 좌표이다.
- 1 ≤ K, M ≤ 100,000
- 1 ≤ K개 점의 각 좌표 ≤ 10^9
- 0 ≤ 삼각형 꼭짓점의 각 좌표 ≤ 10^9
- 모든 삼각형의 넓이는 0이 아니다.
출력
M개의 줄을 출력한다. i번째 줄에는 i번째 삼각형의 내부에 K개의 점 중 적어도 하나가 있으면 Y를, 그렇지 않으면 N을 출력한다.