Birthday Gift
Time Limit: 9000/4500 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 32 Accepted Submission(s): 1
Problem Description
Both Mr. Frog and Wallice love running. Wallice missed Mr. Frog’s birthday recently，so he decided to give a belated birthday gift. He quickly found out an idea： he decided to run a closed curve to contain those meaningful buildings. Unfortunately, he only gets a little time left since he is going to attend an important press conference.
Wallice wants to know the maximal number of buildings can be contained in the closed curve. Note that his speed is 1.
Wallice wants to know the maximal number of buildings can be contained in the closed curve. Note that his speed is 1.
Input
The first line contains only one integer T,which indicates the number of test cases.
For each test case, the first line contains an integer N ($1 \leq N \leq 80$), and a double t ($0 \leq l \leq 5000$) indicating the numbers of buildings Wallice cares about and the time he has.
In the following n lines, the i-th line contains two doubles $x_i, y_i (-600 \leq x_i, y_i \leq 600$) indicating the position of the buildings.
For each test case, the first line contains an integer N ($1 \leq N \leq 80$), and a double t ($0 \leq l \leq 5000$) indicating the numbers of buildings Wallice cares about and the time he has.
In the following n lines, the i-th line contains two doubles $x_i, y_i (-600 \leq x_i, y_i \leq 600$) indicating the position of the buildings.
Output
For each test case，output one line “Case #x: ans’’，where x is the case number (starting from 1) following with ans indicating the maximum number of buildings Wallice can circled in in limited time.
Sample Input
2 4 4.1 0 0 0 1 1 0 1 1 4 3.5 0 0 0 1 1 0 1 1
Sample Output
Case #1: 4 Case #2: 3
Hint
For the second sample, Wallice does not have enough time to circle all the four buildings so he circles three of them instead.
It is guaranteed that the answer would not change even if l changes up to 10^-5, and there would not be any 3 points on one line even if any point changes its position up to 10^-5.