[BalticOI 2005] Polygon
题目描述
给定一个凸包的每条边的长度,求这个凸包。
输入输出格式
输入格式
第一行一个整数 $N$ 代表点数。
接下来 $N$ 行每行一个整数 $a_i$ 代表一条边的长度,其中 $a_i$ 代表第 $i$ 个点与第 $i+1$ 个点之间的边的长度,$a_n$ 代表第 $n$ 个点与第 $1$ 个点之间的边的长度。
输出格式
$N$ 行每行两个实数 $x_i,y_i$ 代表一个点的坐标。(需要满足 $|x_i|,|y_i| \le 10^7$)
如果有多组解任意输出一组即可。
如果无解输出 `NO SOLUTION`。
**注意请按照逆时针输出输出凸包上的点。**
虽然原题说顺时针或逆时针顺序输出皆可,但是在本题中 **请严格按照逆时针方向输出**。
不一定必须按照编号的顺序输出,比如说点 $P_1\to P_2 \to P_3$ 是逆时针顺序,那么按照 $P_2 \to P_3 \to P_1$ 也可。
输入输出样例
输入样例 #1
4
7
4
5
4
输出样例 #1
0.5 2.5
7.5 2.5
4.5 6.5
0.5 6.5
说明
#### 样例说明
对于样例 $1$:
![](https://cdn.luogu.com.cn/upload/image_hosting/7bbhlpom.png)
#### 数据规模与约定
对于 $100\%$ 的数据,$3 \le N \le 1000$,$1 \le a_i \le 10^4$。
**本题使用 Special Judge。**
感谢 spj 作者 @[tiger2005](https://www.luogu.com.cn/user/60864)。
#### 说明
翻译自 [BalticOI 2005 Day2 C Polygon](https://boi.cses.fi/files/boi2005_day2.pdf)。