Cube Killer |
The world is facing a great crisis. The ancient prophecy is true. The Giant Cube is on its way to destroy earth. As a brilliant programmer, you have to develop a small module for the Cube-Killer Super Computer. This problem describes the task of that module.
For this problem, you will be given a list of three dimensional points with integer coordinates. You have to calculate the side-length of the smallest cube such that, the cube is axis parallel and all of the given points lie on its surface.
Notes:
The first line contains an integer T (T < 101) that denotes the number of test cases. The first line of each test case contains N ( 2N20000), the number of points to be processed. Each of the following N lines contains three space separated integers x y z denoting the co-ordinates of a point in three dimensions. The absolute value of x, y and z doesn't exceed 1000000000 (109). All the points will be distinct.
Input file is huge please use faster input and output methods (e.g. printf and scanf in C++).
For each input, print the output in the format, `Case X: Y' (here, X is the serial of the input and Y is the answer). If there is no cube such that all of the given points lie on its surface then print `-1', otherwise print the side length of the smallest such cube.
2 3 0 0 0 1 2 1 2 0 1 3 0 0 0 1 1 1 2 2 2
Case 1: 2 Case 2: -1
Problemsetter: Md. Moshiur Rahman
Special Thanks: F. A. Rezaur Rahman Chowdhury