Problem C. Chain of Circles ≡

Statement

Given an ordered set of two-dimensional points specified by their coordinates (x_i, y_i),
you must construct circles between each pair of consecutive points with indices i and i + 1 such that:

• Only tangential intersections are allowed between boundaries of consecutive circles.
  It means that boundaries must either touch at a single point or completely overlap.
• The radius of the largest circle must be minimized.

The task is to output the coordinates of the centers of such circles.

Input format

The first line contains the number of points, n.
The next line contains 2 × n floating-point numbers: the coordinates (x_i, y_i) of the points.

Output format

Output the coordinates of the circle centers with a precision of 10 decimal places.

Constraints

It is guaranteed that a solution exists.
The maximum radius of any circle does not exceed 100.

 − 10 ≤ (x_i, y_i) ≤ 10, |x_i + 1 − x_i| + |y_i + 1 − y_i| > 0,
2 ≤ n ≤ 500.

Sample tests

4
-1.00000 -2.00000
 1.50000 -1.50000
 3.00000  1.00000
 1.00000  4.00000

 0.2758620685 -1.8793103423
 3.3684210571 -0.9210526343
 2.6315789438  2.9210526292

3
-1.50000  0.50000
-2.50000  3.50000
 3.50000 -1.50000

-1.0714285714  2.3095238095
 0.5000000000  1.0000000000