How To Make Stars

Time Limit : 2 sec, Memory Limit : 262144 KB

E: 星の作り方 - How To Make Stars -

物語

北ノ木坂学院1年生の星屑鈴だニャ!鈴はお星様がだ〜い好き!夜はいつも幼馴染の花代ちんと一緒に,こっそりと学校の屋上でお星様を見てるんだ!だけど,今日のお天気はあいにくの雨・・・.これじゃ,お星様を見ることができないニャ!花代ちんどうしよう〜!

鈴「・・・ああっ!いいこと思い付いたニャ!色んなお星様を見れるような,おっきなプラネタリウムを作るニャ!花代ちん!さっそくやるニャ!」

花代「えっ,えぇっ,鈴ちゃんちょっと待って!プラネタリウムの作り方なんて,私知らないよ!」

鈴「大丈夫ニャ!2人で力を合わせればきっとできるよ!ニャニャニャニャ〜!」

花代「だ,ダレカタスケテ〜!」

問題

自己交差のない多角形の中で,頂点数が10でありかつ,任意の頂点から一定の方向に周上をたどったとき,内角が30度以上60度以下である部分と,内角が240度以上270度以下である部分が交互に現れるものを「星」と定義する.

星は面積によって階級が定まる.具体的には,面積が S_1 以上のものを1級星, S_{i−1}より小さくS_i以上のものをi級星 (i ≥ 2) と呼ぶように階級を付ける.

階級がn個あるとして,階級の目安となるn種類の面積S_1, ..., S_nが与えられるので,各k (1 ≤ k ≤ n)についてk級星となる星を作り,2次元平面上に配置せよ. ただし,各星が互いに重なってはならない.

入力形式

入力は以下の形式で与えられる.

n
S_1 ... S_n

1行目には階級の数nが与えられる. 2行目には,階級の目安となる面積を表す整数S_1からS_nが順に空白区切りで与えられる.

入力は以下の制約を満たす.

  • 1 ≤ n ≤ 100
  • 1 ≤ S_i ≤ 100,000 (1 ≤ i ≤ n)
  • i < jならばS_i > S_j

出力形式

全ての階級の星について,1行目には階級を表す整数kを,続く10行には任意の頂点から反時計回りで10個の頂点の座標(x, y)を1行ごとに出力せよ.頂点の座標(x, y)xyを空白区切りで出力せよ.星は,1級星から順に出力せよ.すなわち,出力は以下のようになる.

1級星の出力
...
n級星の出力

k級星の星については,以下のように出力する.

k
x_1 y_1
...
x_{10} y_{10}

ただし,座標の絶対値が5,000を超えてはならない.また,出力が非常に大きくなる可能性があるため,座標値の出力は小数点以下9桁までとせよ.

星の内角について,指定の範囲からの絶対誤差を10^{−3}rad(ラジアン)まで許す.

星が互いに交差することや,接触していること,ある星が他の星に内包されるといったことは許されない.ここで,星が接触しているとは,異なる星に含まれる任意の2辺の距離が10^{−7}以下であるときを指す.

1級星の面積はS_1以上,i級星 (i ≥ 2) の面積はS_{i−1}未満S_i以上でなければならないが,絶対誤差を10^{−7}まで許す.

1つの星を構成する任意の2頂点間の距離は10^{−3}以上でなければならない.

入力例1

2
10 5

出力例1

1
-10.00 -6.48
-10.79 -8.91
-13.34 -8.91
-11.28 -10.41
-12.07 -12.84
-10.00 -11.34
-7.93 -12.84
-8.72 -10.41
-6.66 -8.91
-9.21 -8.91
2
10.00 12.34
9.47 10.72
7.77 10.72
9.15 9.72
8.62 8.10
10.00 9.10
11.38 8.10
10.85 9.72
12.23 10.72
10.53 10.72

入力例2

3
10 8 5

出力例2

1
-10.00 -6.48
-10.79 -8.91
-13.34 -8.91
-11.28 -10.41
-12.07 -12.84
-10.00 -11.34
-7.93 -12.84
-8.72 -10.41
-6.66 -8.91
-9.21 -8.91
2
10.00 12.93
9.34 10.91
7.21 10.91
8.94 9.65
8.28 7.63
10.00 8.88
11.72 7.63
11.06 9.65
12.79 10.91
10.66 10.91
3
20.00 22.34
19.47 20.72
17.77 20.72
19.15 19.72
18.62 18.10
20.00 19.10
21.38 18.10
20.85 19.72
22.23 20.72
20.53 20.72

Source: Aizu Competitive Programming Camp 2015 Day3 , Japan, 2015-09-23