I. 凹包
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

给定一个包含 $$$n$$$ 个点的二维点集 $$$P$$$ 。 我们定义点集 $$$P$$$ 的一个凹包为 ： 从 $$$P$$$ 中选出若干个点作为顶点 ， 按某种顺序连接而成的简单多边形 ， 满足其面积严格大于 $$$0$$$ ， 且凹 （即多边形内部至少存在一个内角严格大于 $$$180^\circ$$$ ） 。

现在共有 $$$q$$$ 次独立的询问 。 每次询问给定一条线段 $$$S$$$ ， 请你判断 ： 是否存在至少一个由 $$$P$$$ 的子集构成的合法凹包 ， 使得该凹包 （包含其内部与边界） 与线段 $$$S$$$ 有交集 ？

凹包
Input

第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ( $$$3 \le n \le 2 \times 10^5$$$ , $$$1 \le q \le 2 \times 10^5$$$ ) ， 分别表示点集 $$$P$$$ 中的点的数量以及询问的次数 。

接下来的 $$$n$$$ 行 ， 每行包含两个整数 $$$x$$$ 和 $$$y$$$ ( $$$-10^9 \le x , y \le 10^9$$$ ) ， 表示点集 $$$P$$$ 中一个点的坐标 。 数据保证这 $$$n$$$ 个点互不相同 。

接下来的 $$$q$$$ 行 ， 每行包含四个整数 $$$x_1$$$ , $$$y_1$$$ , $$$x_2$$$ 和 $$$y_2$$$ ( $$$-10^9 \le x_1 , y_1 , x_2 , y_2 \le 10^9$$$ ) ， 表示一次询问中线段 $$$S$$$ 的两个端点分别为 $$$(x_1, y_1)$$$ 和 $$$(x_2, y_2)$$$ 。 数据保证每次询问的线段端点不重合 。

Output

对于每次询问 ， 如果存在至少一个合法的凹包与线段 $$$S$$$ 相交 ， 请在一行中单独输出 Yes ； 否则 ， 输出 No 。

Example
Input
5 2
0 0
4 0
4 4
0 4
2 2
-1 -1 -2 -2
1 1 5 5
Output
No
Yes
Note

对于唯一的一组样例 ：

第一组询问 ， 给定线段从 $$$(-1, -1)$$$ 到 $$$(-2, -2)$$$ 。 该线段绝对无法与任何可能的凹包相交 ， 答案为 No 。

第二组询问 ， 给定线段从 $$$(1, 1)$$$ 到 $$$(5, 5)$$$ 。

我们可以构造多边形 $$$(0, 0)$$$ $$$(4, 0)$$$ $$$(4, 4)$$$ $$$(2, 2)$$$ $$$(0, 4)$$$ ， 这是一个合法的凹包 ， 与该线段相交 ， 因此答案为 Yes 。