Description

Given the length of each edge of a convex hull, construct this convex hull.

Input Format

The first line contains an integer $N$, representing the number of points.

The next $N$ lines each contain an integer $a_i$, representing the length of one edge. Here, $a_i\ (i<n)$ is the length of the edge between the $i$-th point and the $(i+1)$-th point, and $a_i\ (i=n)$ is the length of the edge between the $n$-th point and the $1$-st point.

Output Format

Output $N$ lines. Each line contains two real numbers $x_i, y_i$, representing the coordinates of a point. (They must satisfy $|x_i|, |y_i| \le 10^7$.)

If there are multiple solutions, output any one of them.

If there is no solution, output NO SOLUTION.

Requirements for judging on Luogu

Note: please output the points on the convex hull in counterclockwise order.

Although the original statement allows either clockwise or counterclockwise order, in this problem you must output strictly in counterclockwise order.

You do not have to output in the original numbering order. For example, if $P_1 \to P_2 \to P_3$ is counterclockwise, then $P_2 \to P_3 \to P_1$ is also acceptable.

4
7
4
5
4 

0.5 2.5
7.5 2.5
4.5 6.5
0.5 6.5 

Hint

Sample Explanation

For sample $1$:

Constraints

For $100\%$ of the testdata, $3 \le N \le 1000$, $1 \le a_i \le 10^4$.

This problem uses Special Judge.

Thanks to the spj author

Notes

Translated from BalticOI 2005 Day2 C Polygon.

Translated by ChatGPT 5