KTH Challenge 2015 Warm-up


2015-04-21 23:00 CEST

KTH Challenge 2015 Warm-up


2015-04-26 11:00 CEST
The end is near!
Contest is over.
Not yet started.
Contest is starting in -882 days 14:04:13

Time elapsed


Time remaining


Problem D

Tomosynthesis is a medical imaging modality in which a 3D dataset is obtained algorithmically from a set of X-ray images taken in different directions within a limited range of angles. A larger range of angles normally gives a better reconstruction, but is more difficult to acquire. Arvid is working on a reconstruction algorithm for obtaining the 3D image, but so far it doesn’t seem to work when there are overlapping structures in any of the input images. The sample he will first reconstruct is a test object consisting of parallel equal-length cylinders of varying diameters that will be rotated around the axis of the cylinders.

\includegraphics[width=0.5\textwidth ]{phantom}
Figure 1: To the left, a cross section of the test object of sample input 1. The upper projection is not acceptable since the two larger cylinders overlap. In the lower projection no cylinders overlap, so this direction and a range of angles around it are okay. To the right, an illustration of the same test object from the side.

Disregarding the fact that his algorithm will not work in practice, Arvid asks you for help. What is the largest range of angles in which the test object can be imaged without any cylinders overlapping in any of the images? An image is a plane projection of the structure perpendicular to the axes of the cylinders.


The first line of input contains a single integer $2\leq N\leq 100$ denoting the number of cylinders that constitute the test object. This is followed by $N$ rows, each containing three floating point numbers $x$, $y$ and $r$, denoting the $x$- and $y$-coordinate of the center of a cylinder, and the radius of that cylinder, respectively. The coordinates are in the range $-1\, 000\leq x,y \leq 1\, 000$ and the radius $0<r\leq 1\, 000$. None of the cylinders touch or overlap.


Output a single number, the size in radians of the largest continuous range of projection directions over which no cylinders overlap. If no such angle exists output 0. Your answer should have an absolute error of at most $10^{-8}$.

Sample Input 1 Sample Output 1
-1 -1 0.5
1 -1 0.25
1 1 1
Sample Input 2 Sample Output 2
0 0 1
2 2 1