Hatena::Grouptopcoder

じじいのマラソン反省会@TopCoder

ニコニコ生放送:red.cliff.jp
TopCoderでプログラムしてみた(Algorithm Single Round Match専用):http://red.cliff.jp/topcoder.html
 | 

2011-06-29

問題

00:56

複数の点がだいたいランダムに配置されている(点の数は50~5000)。それらの点を結んで多角形を作れ。

  • 入力パラメータsidesDiff。1≦sidesDiff≦20。sidesDiffは多角形の各辺の、最小の長さと最長の長さの割合、もしsidesDiffが20だったら、最小の辺の長さは、最長の辺の長さの100-20=80%以上でないといけない。
  • 入力パラメータradiiDiff。1≦radiiDiff≦20。radiiDiffはは多角形の中心(点の座標の平均)から、各頂点からの距離の、最小の長さと最長の長さの割合。sidesDiffと同様。
  • 同じ点を2回以上使ってはいけない。
  • n角形につきn*n点もらえる。

点が少ないケース(Example1)

f:id:shindannin:20110630004059j:image

点が多いケース(Example7200)

f:id:shindannin:20110630004423j:image

このように、つくるべき多角形は正多角形に近い形になります。

 |