Center

The first practical homework. The deadline is 24.4.2017 (before the turorial).

Problem description

Given a finite set of points S of 3-dimensional space, find a point p which Manhattan distance to the most distant point of S is minimal.

Data format

Your program must read an instance of the problem from the standard input and result must be printed on the standard output. On the input, the first line of contains the number of points of S and each of the following |S| lines contain coordinates one point of the input.

The standard output must contain the following consecutive four lines. The first line must be #OUTPUT:. The second line must be the maximal Manhattan distance between the point p to a point of S. The third line must contain the coordinates of the point p. The last line must be #OUTPUT END.

Example input


8
0 1 1
4 1 1
0 7 1
4 7 1
1 0 3
4 1 5
0 7 5
4 7 5

Example output


#OUTPUT:
7
2 4 3
#OUTPUT END

Submitting your solution

Send an e-mail to your teaching assistant with
  • source code used to get your results (in case it consists of multiple files, please use ZIP or TAR to pack them),
  • how to compile your program (use Makefile in case it consists of multiple files), and
  • description of your algorithm in the PDF format.

Evaluation

Your program must produce a correct answer for arbitrary input, assuming sufficient amount of memory and time is provided. The main criteria determining the number of points received from this homework is the running time on inputs similar to the test ones. A trivial algorithm finds optimal solutions in one hour but it should not be hard to improve the algorithm to obtain expected results in one minute.

The quality of source codes and documentation is also considered.

Test data

A pack of testing inputs.

Rules

  • All the code which you submit must be original created by you without any external "inspiration".
  • Do not share your solution with anyone else so that your code does not become someone else's "inspiration". The only exception to this rule is submitting the assignment.
  • Your solution should be written in either C/C++, Java, C#, BASH (awk) or Python. Your teaching assistant may allow using other programming languages.
  • In order to solve (integer) linear programming problems, the library GLPK or program GLPSOL can be used. Linear programming problem can also be formulated in the modelling language MathProg and then solved by GLPSOL. Your teaching assistant may allow using other solvers.
  • Your program must be easily compilable and it must run on GNU/Linux without any non-trivial dependencies (decided by your teaching assistant). For instance in C++, it should be sufficient the standard library and glpk.
  • Programs producing output in an incorrect format are rejected.

Hints

  • Read this page carefully.
  • Try to run your program in the Unix laboratory at Mala Strana to avoid unnecessary bugs.