Police and Thieves
All submissions for this problem are available.### Read problem statements in [Hindi](http://www.codechef.com/download/translated/LTIME74/hindi/POLICE.pdf), [Bengali](http://www.codechef.com/download/translated/LTIME74/bengali/POLICE.pdf), [Mandarin Chinese](http://www.codechef.com/download/translated/LTIME74/mandarin/POLICE.pdf), [Russian](http://www.codechef.com/download/translated/LTIME74/russian/POLICE.pdf), and [Vietnamese](http://www.codechef.com/download/translated/LTIME74/vietnamese/POLICE.pdf) as well. There are $N$ police officers numbered $1$ through $N$ and $M$ thieves numbered $1$ through $M$. All people (police officers and thieves) are points in a Cartesian plane. Let's denote the coordinates of the $i$-th officer by $(Xp_i, Yp_i)$, and the coordinates of the $i$-th thief by $(Xt_i, Yt_i)$. A thief is *arrested* if there is a subset of police officers which form a convex polygon such that the thief is located strictly inside that polygon. The police station wants to send reinforcements ― zero or more police officers ― to make sure all the thieves are arrested. The coordinates of these additional officers may be chosen arbitrarily (they may be any real numbers); it is not allowed to move the officers which were present initially. Calculate the minimum number of police officers that need to be sent as reinforcements in order to arrest all the thieves. ### Input - The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows. - The first line of each test case contains two space-separated integers $N$ and $M$. - $N$ lines follow. For each $i$ ($1 \le i \le N$), the $i$-th of these lines contains two space-separated integers $Xp_i$ and $Yp_i$. - $M$ more lines follow. For each $i$ ($1 \le i \le M$), the $i$-th of these lines contains two space-separated integers $Xt_i$ and $Yt_i$. ### Output For each test case, print a single line containing one integer ― the minimum number of additional police officers. ### Constraints - $1 \le T \le 10$ - $0 \le N \le 10^5$ - $1 \le M \le 10^5$ - $|Xp_i|, |Yp_i| \le 2*10^8$ for each valid $i$ - $|Xt_i|, |Yt_i| \le 2*10^8$ for each valid $i$ - no two people (police officers or thieves) have the same position ### Subtasks **Subtask #1 (40 points):** $N, M \le 1,000$ **Subtask #2 (60 points):** original constraints ### Example Input ``` 1 1 1 10 10 20 20 ``` ### Example Output ``` 2 ```
|Tags||convex-hull, cornercase, erfaniaa, geometry, ltime74, medium|
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, SQL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.