#P18667. Master of Polygon
Master of Polygon
Master of Polygon
Prof.Chen 是计算几何大师。现在,他在欧几里得平面上有一个包含 个顶点的简单多边形,并想向你提出 个询问。
每个询问给出两个点 。你需要判断线段 是否与给定多边形的边界相交。
注意,即使线段只是接触多边形边界上的某一点,也必须回答 YES。这包括接触顶点、端点落在边上,以及与某条边共线重合。线段完全在多边形内部但不接触边界时,回答 NO。
输入格式
第一行包含两个整数 ,满足 、,分别表示多边形的顶点数和询问数。
接下来的 行,每行包含两个整数 ,满足 ,表示一个顶点的坐标。顶点按顺时针或逆时针顺序给出,最后一个顶点与第一个顶点相连。
保证多边形是简单多边形:顶点两两不同;除了相邻的两条边在公共顶点处接触以外,任意两条边都不相交,也不接触。此外,任意两条相邻边不共线。
接下来的 行,每行包含四个整数 ,满足 ,表示询问线段的两个端点 、。保证每个询问的两个端点不重合。
本题只有一组数据,输入开头没有测试组数。
输出格式
对于每个询问,输出一行。如果闭线段 与多边形边界有公共点,输出 YES;否则输出 NO。
样例输入 1
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
样例输出 1
YES
YES
YES
YES
NO
YES