#1416. [Ynoi2024] 堕天作战/虚空处刑

[Ynoi2024] 堕天作战/虚空处刑

题目描述

给你 nn 个二维欧氏平面上的点,这些点中编号相邻的两个点进行连边,构成一个简单多边形,你需要进行 qq 次询问。

一个多边形是简单多边形,当且仅当其所有结点都不同,并且对该简单多边形的任意两条边,都不会发生相交或者在某点接触,除非这两条边在多边形上是相邻的两条边,这种情况下两条边可以在结点处相交。保证相邻的两条边不会共线。

对每个询问,给定两个点 PP 和 QQ,你需要判断线段 PQPQ 是否和该简单多边形相交。注意到如果线段恰好经过该简单多边形上的某个点,你也需要回答是。

输入格式

第一行包含两个数 nn 和 qq,表示点的个数和询问的个数。

之后的 nn 行,每行包含两个整数 xx 和 yy,表示简单多边形上的一个点 (x,y)(x,y)。所有多边形上的点要么是顺时针顺序给出,要么是逆时针顺序给出。

接下来 qq 行每行包含四个整数 x1,y1,x2x_1,y_1,x_2 和 y2y_2,表示查询的两个端点 P(x1,y1)P(x_1,y_1) 和 Q(x2,y2)Q(x_2,y_2)。保证所有给定的询问的所有端点都互不相同。

输出格式

对每个询问,输出一行一个字符串表示答案。

如果该线段和简单多边形有交,则输出 YES,否则输出 NO。

样例

4 6
1 1
4 1
4 4
1 4
0 2 2 0
0 1 1 1
0 0 5 5
2 2 4 2
2 2 3 2
5 1 0 2
YES
YES
YES
YES
NO
YES

题目来源:洛谷 P11370