TopCoder problem "GetThemAll" used in SRM 207 (Division I Level Three)



Problem Statement

    You have an infinite chessboard with several black pieces placed on it. You have a white knight on the same chessboard, which starts from the (0, 0) point, and you want to know how fast it can capture all the black pieces.



You will be given a String[] pieces, containing information about black pieces. Each element of pieces will be formatted as "X Y", where X and Y are integer numbers between -1000000 and 1000000, inclusive. Your method should return the minimum number of moves needed to capture all the black pieces, assuming none of them move.
 

Definition

    
Class:GetThemAll
Method:quickKnight
Parameters:String[]
Returns:int
Method signature:int quickKnight(String[] pieces)
(be sure your method is public)
    
 

Notes

-A knight's jump moves him 2 cells along one of the axes, and 1 cell along the other one. In other words, if a knight is at (0,0), it may move to (-2, -1), (-2, 1), (2, -1), (2, 1), (-1, -2), (1, -2), (-1, 2) or (1, 2).
-The knight starts at (0, 0).
 

Constraints

-pieces will contain between 0 and 9 elements, inclusive.
-Each element of pieces will be formatted as "X Y", where X and Y are integer numbers without extra leading zeroes.
-X and Y will be between -1000000 and 1000000, inclusive, in each element of pieces.
-All elements of pieces will be different.
-There are no pieces at (0, 0).
 

Examples

0)
    
{"1 2"}
Returns: 1
Just one move.
1)
    
{"2 -1", "2 1", "-2 1", "-2 -1"}
Returns: 7
The knight should return to the starting position several times.
2)
    
{"0 1"}
Returns: 3
The knight needs 3 jumps to move to any adjacent cell.
3)
    
{"0 7", "7 7", "7 0"}
Returns: 15
4)
    
{"-1000000 -1000000", "1000000 1000000", "1000000 -1000000", "-1000000 1000000"}
Returns: 3666668
One really big square, containing the maximal possible distance between two pieces.

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=2926

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=5853&pm=2926

Writer:

Olexiy

Testers:

PabloGilberto , lbackstrom , brett1479

Problem categories:

Brute Force, Math