bzoj#P1769. [Ceoi2009] Tri

[Ceoi2009] Tri

题目描述

You are given KK points with positive integer coordinates. You are also given MM triangles, each of them having one vertex in the origin and the other 22 vertices with non-negative integer coordinates.

You are asked to determine for each triangle whether it has at least one of the KK given points inside. (None of the KK points are on any edge of any triangle.)

输入格式

The first line will contain KK and MM.

The following KK lines will contain 22 positive integers x,yx,y separated by one space that represent the coordinates of each point.

The next MM lines have 44 non-negative integers separated by one space, (x1,y1)(x_1,y_1) and (x2,y2)(x_2,y_2), that represent the other 22 vertices of each triangle, except the origin.

输出格式

The output should contain exactly MM lines. The kthk^{th} line should contain the character Y if the kthk^{th} triangle (in the order of the input file) contains at least one point inside it, or N otherwise.

样例

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 3
1 2
1 3
5 1
5 3
1 4 3 3
2 2 4 1
4 4 6 3 
Y
N
Y

样例说明

数据规模与约定

In 50%50\% of the test cases, all triangles have vertices with coordinates x1=0x_1=0 and y2=0y_2=0. That is, one edge of the triangle is on the x-axis, and another is on the y-axis.

In 100%100\% of the test cases, 1K,M1051\leq K,M\leq 10^5, $1\leq\text{each coordinate of the } K \text{ points}\leq 10^9$, $0\leq\text{each coordinate of the triangle vertices}\leq 10^9$, Triangles are not degenerate (they all have nonzero area).

题目来源

Ceoi2009