Squares
The first practical homework. The deadline is 10.4.2016.Problem description
A square at the center in the point [r_1, r_2] with sides of length s is the square with vertices {[r_1 + s_1, r_2 + s_2]; s_1, s_2, \in {-s/2, s/2}}.An input of the problem is a set of points b_1, ..., b_n. For every point b_i, you have to assign a square at the center b_i with sides of length a_i >= 0. The area of the intersection of every pair of squares has to be zero, i.e. the intersection has to be at most an side. For instance, you can assign to points [0,0] and [5,4] squares with sides of lenth 2 and 1, or 6 and 4, or 10 and 0; however, sides of length 4 and 7 are forbidden. If a square has a side of length 0, then it is allowed to lie on a side (vertex) of a square but it must not lie inside another square. Your task is to write a program that assign a square to every point so that the sum of length of side of all squares is maximized.
You can assume that every input contains at least two points. Think over that there always exists an optimal solution although it may not be unique.
Data format
Your program must read an instance of the problem from the standard input and result must be printed on the standard output. The first line of contains the number of points n. Next n lines contain coordinates of each points b_1, ..., b_n. The output must contains n lines where the length of side of i-the square in on i-th line.Example input
3
3 4
5 2
-8 -5
Example output
0
4
22
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 maximal size of an instance that your program solves in one minute.The quality of source codes and documentation is also considered.
Test data
There are two packs of inputs to be used for testing; one has between 10 and 30000 points [356 KB] and the other has between 100000 and 10000000 points [114 MB]. Your program will be tested on different but similar inputs. The following table shows running time of three different programs on test data (measured in seconds).
| Number of points | Trivial algorithm | Expected algorithm | Advanced algorithm |
|---|---|---|---|
| 10 | <1 | <1 | <1 |
| 100 | <1 | <1 | <1 |
| 300 | <1 | <1 | <1 |
| 1000 | 8 | <1 | <1 |
| 3000 | 251 | <1 | <1 |
| 10000 | >300 | 2 | <1 |
| 30000 | >300 | 15 | <1 |
| 100000 | >300 | 175 | <1 |
| 300000 | >300 | >300 | 2 |
| 1000000 | >300 | >300 | 8 |
| 3000000 | >300 | >300 | 30 |
| 10000000 | >300 | >300 | 119 |
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++ (recommended), 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. Note that the order of line on the output is essential.
Hints
- Read this page carefully.
- Be careful on numerical problems, especially in producing the result. Although it may not be obvious, there always exist optimal solutions which is integer. It is not necessary to find an integer solution, using integers reduces numerical errors.
- Try to run your program in the Unix laboratory at Mala Strana to avoid unnecessary bugs.