## Boomerang

View as PDF

Points: 12 (partial)
Time limit: 25.0s
Memory limit: 1G

Author:
Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig
##### Facebook Hacker Cup 2015 Round 3

Today you've found yourself standing on an infinite 2D plane at coordinates . There are also targets on this plane, with the one at coordinates .

You have a boomerang which you can throw in a straight line in any direction from your initial location.
After you throw it, you may instantaneously run to any location on the plane. After the boomerang has travelled a distance of exactly along its initial trajectory, it will return directly to you — that is, to your chosen final location. Note that you cannot move around once the boomerang has started its return trip — its path will always consist of 2 line segments (the first of which has a length of exactly ). The boomerang and the targets have infinitesimal size.

Let be the number of targets which your boomerang hits (directly passes through) during the first segment of its flight, and be the number of targets which it hits during the second segment. Your throw is then awarded a score of . What's the maximum score you can achieve? Note that, if there is a target at the exact location at which the two segments meet (at a distance of from your initial location), then it counts towards both and !

### Input

Input begins with an integer , the number of planes. For each plane, there is first a line containing the space-separated integers and . The next line contains the integer , and the one after contains the integer . Then, lines follow, the of which contains the space-separated integers and .

### Output

For the plane, print a line containing Case #i:  followed by the maximum score you can achieve.

### Constraints

, for

All coordinates are pairwise distinct. The following restrictions are also guaranteed to hold for the input given:

For any three targets at distinct points , , and , it is guaranteed that is either closer than away from the infinite line between and (and is considered to be on the line), or is further than away (and is considered to not be on the line).

Let be any point at which the boomerang may change direction after hitting a target. For any two targets at distinct points and , it is guaranteed that is either closer than away from the infinite line between and (and is considered to be on the line), or is further than away (and is considered to not be on the line).

### Explanation of Sample

On the first plane, one optimal strategy is to throw the boomerang in the direction of the positive x-axis (that is, to ), and then run to . It will hit targets 2 and 3 on the first segment of its flight, and all 3 targets on the second segment, for a score of .

### Sample Input

5
2 0
2
3
1 0
3 0
4 0
2 0
1
3
1 0
3 0
4 0
5 5
10
4
0 0
10 0
10 10
0 10
0 0
2
6
-1 -1
0 8
0 9
0 10
10 1
10 2
0 0
10
6
-1 -1
0 8
0 9
0 10
10 1
10 2

### Sample Output

Case #1: 6
Case #2: 3
Case #3: 2
Case #4: 1
Case #5: 9