[BOI2005]还原多边形

Grade Open Time Friday, 19 September 2014, 10:08 am
Discount 0.8 Time Discount Friday, 26 September 2014, 10:08 am
Allow late Yes Close Time Friday, 26 September 2014, 10:08 am
Input file boi2005_poly.in Output file boi2005_poly.out

【题目描述】

写一个程序找出一个凸多边形,使得其各条边长等于给定的值。

在这道题中,我们说多边形是凸的,当且仅当其内角严格大于0度且严格小于180度。

【输入格式】

输入文件的第一行有一个整数N,表示多边形边数(3<=N<=1000).

接下来N行每行有一个整数ai,表示多边形一条边的长度(1<=ai<=10000).、

【输出格式】

如果能求出相应的多边形,就输出N行。每行包含两个实数xi,yi(|xi|<=10000000,|yi|<=10000000)。连接(xi,yi)和(xi+1,yi+1)以及(xn,yn)和(x1,y1),要求能得到一个多边形,每条边的长度和给定的相同,但是不要求有相同的顺序。

输出顶点的顺序可以是顺时针也可以是逆时针。

如果这样的凸多边形不存在,输出“NO SOLUTION”。

【样例输入】

4

7

4

5

4

【样例输出】

0.5 2.5

7.5 2.5

4.5 6.5

0.5 6.5

【提示】

样例多边形如图:

【来源】

BOI2005 Polygon