

Monitor the AlpacasTime Limit: 17000/8500 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 629 Accepted Submission(s): 106 Problem Description Coach Zhang has an infinite ranch with N alpacas on it. The alpacas are so lazy that they never move. The $i$th ($1≤i≤N$) alpaca is located at the point ($X_i,Y_i$). Coach Zhang wants to monitor all the alpacas. He found $M$ points where cameras can be placed in his ranch. Coach Zhang only needs to place one camera at a point if he thinks it necessary. An alpaca is monitored when it is on one of the cameras, on the segment between two cameras, or in the triangle formed by three cameras. Now Coach Zhang wants to know the minimum number of cameras required to monitor all the alpacas. Input The first line of input contains an integer $T$, which represents the number of test cases ($T≤20$). Each test case starts with a line containing $N$ and $M$ ($1≤N≤100000,1≤M≤500$). Each of the next N+M lines contains two integers $X$ and $Y$ ($X,Y≤10^9$). The first $N$ lines represent the alpacas’ positions and the last $M$ lines indicate the points that cameras can be placed. Output For each test case, output a single line consisting of “Case #X: Y”. $X$ is the test case number starting from 1. $Y$ is the minimum number of cameras required to monitor all the alpacas. If it is impossible to monitor all the alpacas, you should output 1 instead. Sample Input
Sample Output
Source  
