F.A.Q
Hand In Hand
Online Acmers
Problem Archive
Realtime Judge Status
Authors Ranklist
 
     C/C++/Java Exams     
ACM Steps
Go to Job
Contest LiveCast
ICPC@China
Best Coder beta
VIP | STD Contests
    DIY | Web-DIY beta
Author ID 
Password 
 Register new ID

Monitor the Alpacas

Time 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
3 1 1 0 0 0 0 4 4 0 0 1 0 0 1 -1 0 0 1 1 0 0 -1 -1 0 1 1 0 0 0 1
 

Sample Output
Case #1: 1 Case #2: 3 Case #3: -1
 

Source
 

Statistic | Submit | Discuss | Note
Hangzhou Dianzi University Online Judge 3.0
Copyright © 2005-2024 HDU ACM Team. All Rights Reserved.
Designer & Developer : Wang Rongtao LinLe GaoJie GanLu
Total 0.000000(s) query 1, Server time : 2024-12-11 20:27:05, Gzip enabled