正八角形の分割 2017.4.19 問題

問題の概要

八角形がある。
いくつかの頂点と中心を線分で結ぶ。
このとき、出来る図形が何角形なのかを計算せよ。

出力

入力は
165
こんな感じ。8つの線分に、右図のように 1, 2, 4, 8, 16, 32, 64, 128 の番号が振ってあり、その合計の 10進数が入力となっている。
165 = 1 + 4 + 32 + 128
なので、右図の実線の位置に線分が引かれる。

出力

出力は、出来上がる多角形の頂点数を昇順で。区切り文字は、なし。9角形までしか出てこないので大丈夫。

先ほどの入力の場合、

3角形が 1個
4角形が 2個
5角形が 1個

なので、
3445
と出力すればよい。

補足

不正な入力に対処する必要はない。
少なくとも2箇所は、中心と線分でつながっている頂点がある。
内角が180度の点は頂点ではなく辺の途中。
実装ができた方は Qiitaの記事のコメント欄からリンクを張っていただくと見つけやすくて助かります。
入力も出力も文字列ないしは標準入出力にするのが望ましい。パースも仕事のうち。
この問題は2017年4月19日に開催されるオフラインリアルタイムどう書くF04 の問題です。イベントについては Doorkeeper のページの方を御覧下さい。

サンプルデータ

#	入力	期待	状況へのリンク
0	`165`	`3445`	リンク
1	`80`	`48`	リンク
2	`255`	`33333333`	リンク
3	`68`	`55`	リンク
4	`200`	`355`	リンク
5	`82`	`455`	リンク
6	`164`	`455`	リンク
7	`73`	`455`	リンク
8	`146`	`455`	リンク
9	`37`	`455`	リンク
10	`74`	`455`	リンク
11	`148`	`455`	リンク
12	`41`	`455`	リンク
13	`38`	`355`	リンク
14	`76`	`355`	リンク
15	`152`	`355`	リンク
16	`49`	`355`	リンク
17	`98`	`355`	リンク
18	`196`	`355`	リンク
19	`137`	`355`	リンク
20	`19`	`355`	リンク
21	`20`	`48`	リンク
22	`9`	`57`	リンク
23	`209`	`3345`	リンク
24	`121`	`33345`	リンク
25	`239`	`3333334`	リンク
26	`26`	`347`	リンク
27	`111`	`333344`	リンク
28	`95`	`333344`	リンク
29	`85`	`4444`	リンク
30	`24`	`39`	リンク
31	`97`	`347`	リンク
32	`234`	`33444`	リンク
33	`59`	`33345`	リンク
34	`187`	`333344`	リンク
35	`34`	`55`	リンク
36	`249`	`333335`	リンク
37	`43`	`3445`	リンク
38	`143`	`33335`	リンク
39	`28`	`338`	リンク
40	`79`	`33345`	リンク
41	`173`	`33444`	リンク
42	`55`	`33345`	リンク
43	`77`	`3445`	リンク
44	`35`	`355`	リンク
45	`153`	`3355`	リンク
46	`30`	`3337`	リンク
47	`228`	`3355`	リンク
48	`177`	`3345`	リンク
49	`162`	`445`	リンク
50	`184`	`3345`	リンク

C/C++/Java 用のテストデータ

/*0*/ test( "165", "3445" );    
/*1*/ test( "80", "48" );    
/*2*/ test( "255", "33333333" );    
/*3*/ test( "68", "55" );    
/*4*/ test( "200", "355" );    
/*5*/ test( "82", "455" );    
/*6*/ test( "164", "455" );    
/*7*/ test( "73", "455" );    
/*8*/ test( "146", "455" );    
/*9*/ test( "37", "455" );    
/*10*/ test( "74", "455" );    
/*11*/ test( "148", "455" );    
/*12*/ test( "41", "455" );    
/*13*/ test( "38", "355" );    
/*14*/ test( "76", "355" );    
/*15*/ test( "152", "355" );    
/*16*/ test( "49", "355" );    
/*17*/ test( "98", "355" );    
/*18*/ test( "196", "355" );    
/*19*/ test( "137", "355" );    
/*20*/ test( "19", "355" );    
/*21*/ test( "20", "48" );    
/*22*/ test( "9", "57" );    
/*23*/ test( "209", "3345" );    
/*24*/ test( "121", "33345" );    
/*25*/ test( "239", "3333334" );    
/*26*/ test( "26", "347" );    
/*27*/ test( "111", "333344" );    
/*28*/ test( "95", "333344" );    
/*29*/ test( "85", "4444" );    
/*30*/ test( "24", "39" );    
/*31*/ test( "97", "347" );    
/*32*/ test( "234", "33444" );    
/*33*/ test( "59", "33345" );    
/*34*/ test( "187", "333344" );    
/*35*/ test( "34", "55" );    
/*36*/ test( "249", "333335" );    
/*37*/ test( "43", "3445" );    
/*38*/ test( "143", "33335" );    
/*39*/ test( "28", "338" );    
/*40*/ test( "79", "33345" );    
/*41*/ test( "173", "33444" );    
/*42*/ test( "55", "33345" );    
/*43*/ test( "77", "3445" );    
/*44*/ test( "35", "355" );    
/*45*/ test( "153", "3355" );    
/*46*/ test( "30", "3337" );    
/*47*/ test( "228", "3355" );    
/*48*/ test( "177", "3345" );    
/*49*/ test( "162", "445" );    
/*50*/ test( "184", "3345" );