Description

For a set $S$ of points in the plane and a point $p$ in the plane, define the function $f(p, S)$ to be $1$ if and only if $p$ lies inside the convex hull of $S$ (including its boundary), and $0$ otherwise.

Given two sets of points in the plane $P=\{p_1,p_2,\cdots,p_N\}$ and $A=\{a_1,a_2,\cdots,a_M\}$, we call a point $a_i \in A$ an extreme point if and only if

That is, $a_i$ is not inside the convex hull formed by $P$ together with any other single point from $A$.

Please count the number of extreme points in set $A$.

Input Format

• The first line contains two space-separated positive integers $N$ and $M$.
• The second line contains $N$ space-separated pairs of integers; the $i$-th pair $(x_i^p,y_i^p)$ denotes the coordinates of point $p_i$.
• The third line contains $M$ space-separated pairs of integers; the $j$-th pair $(x_j^a,y_j^a)$ denotes the coordinates of point $a_j$.
• For the same set, the input guarantees that no two points share identical coordinates.

Output Format

Output a single line with a single integer, the number of extreme points in set $A$.

4 5 
6 3 7 -1 -6 -5 1 5
-5 -5 7 -5 9 -9 -10 11 -5 -6

3

Hint

Constraints:

• For $30\%$ of the testdata, $N,M\le 50$.
• For another $30\%$ of the testdata, $N\le 10, M\le 20000$.
• For $100\%$ of the testdata, $3\le N\le 10^5, 1\le M\le 10^5,\ |x_i|,|y_i|\le 10^6$, and the convex hull of set $P$ has non-zero area.

Translated by ChatGPT 5