灰灰的地图
出题人太菜,暂无测试数据。
题目描述
灰灰和他的伙伴一起玩RealAU,他对RealAU中判断点与边界关系的功能产生了兴趣。现在灰灰有\(N\)条有向线段,每条线段由两对坐标\((a_x, a_y), (b_x, b_y)\)分别表示起点和终点。保证线段最终能围成一个闭合图形,且不会出现回形结构。现对于\(Q\)次询问,每次给出一个点\((c_x, c_y)\),请问该点是否在闭合图形内,并输出Yes
orNo
(在边界上则输出Yes
)
输入输出格式
输入格式
第一行两个整数,\(N, Q, u, v\)。其中\((u, v)\)是围栏内一点,不在边界上
接下来\(N\)行,每行四个整数\(a_x, a_y, b_x, b_y\)表示一条有向线段
接下来\(Q\)行,每行两个整数\(c_x, c_y\)表示一组询问
输出格式
每组询问回答Yes
orNo
并换行
样例
输入
8 6 2 2
1 1 2 8
1 1 5 1
5 1 6 4
8 3 7 1
7 1 10 1
8 3 6 4
10 1 10 8
10 8 2 8
5 6
7 3
8 3
1 5
11 4
9 2
输出
Yes
No
Yes
No
No
Yes
样例解释
如图,注意\(P_3\)在边界上
数据范围
对于所有数据,\(N \leqslant 1000, Q \leqslant 100, a_x, a_y, b_x, b_y, c_x, c_y \leqslant 10^9\)
信息
- ID
- 1059
- 难度
- 10
- 分类
- (无)
- 标签
- (无)
- 递交数
- 1
- 已通过
- 0
- 通过率
- 0%
- 上传者