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)はxとyを空白区切りで出力せよ．星は，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

Note

Link

 

---