P4023 [CTSC2012] Extreme Point Statistics

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 $$\sum_{j\ne i} f(a_i,P\cup\{a_j\})=0.$$ 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$.

- 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 a single line with a single integer, the number of extreme points in set $A$.

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