#P18667. Master of Polygon

    ID: 18003 传统题 4000ms 1024MiB 尝试: 1 已通过: 1 难度: 10 上传者: 标签>CF3200NOI/NOI+/CTS分治算法离线查询查询排序普通并查集Li Chao 线段树离散化二分查找线段相交有理数精确运算

Master of Polygon

Master of Polygon

Prof.Chen 是计算几何大师。现在,他在欧几里得平面上有一个包含 nn 个顶点的简单多边形,并想向你提出 qq 个询问。

每个询问给出两个点 P,QP,Q。你需要判断线段 PQPQ 是否与给定多边形的边界相交。

注意,即使线段只是接触多边形边界上的某一点,也必须回答 YES。这包括接触顶点、端点落在边上,以及与某条边共线重合。线段完全在多边形内部但不接触边界时,回答 NO。

输入格式

第一行包含两个整数 n,qn,q,满足 3≤n≤2000003\le n\le200000、1≤q≤2000001\le q\le200000,分别表示多边形的顶点数和询问数。

接下来的 nn 行,每行包含两个整数 x,yx,y,满足 0≤x,y≤300000\le x,y\le30000,表示一个顶点的坐标。顶点按顺时针或逆时针顺序给出,最后一个顶点与第一个顶点相连。

保证多边形是简单多边形:顶点两两不同;除了相邻的两条边在公共顶点处接触以外,任意两条边都不相交,也不接触。此外,任意两条相邻边不共线。

接下来的 qq 行,每行包含四个整数 x1,y1,x2,y2x_1,y_1,x_2,y_2,满足 0≤x1,y1,x2,y2≤300000\le x_1,y_1,x_2,y_2\le30000,表示询问线段的两个端点 P(x1,y1)P(x_1,y_1)、Q(x2,y2)Q(x_2,y_2)。保证每个询问的两个端点不重合。

本题只有一组数据,输入开头没有测试组数。

输出格式

对于每个询问,输出一行。如果闭线段 PQPQ 与多边形边界有公共点,输出 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