hotpepsiの練習帳

TCO15 Marathon Round1

21:09

https://competitiveprogramming.info/topcoder/marathon/round/16445

SmallPolygons

問題

• 2次元座標上にてNP個の頂点が与えられる
• 頂点を線で結び、1個以上N個以内の多角形を作れ
• ただし、各頂点は必ずいずれかの多角形に属すること
• それぞれの線分は交わらないこと

方針

• 近い座標同士で三角形の候補を作る
• 面積が近いもの同士をマージしていく
• https://github.com/firewood/topcoder/blob/master/marathon/tco15r1/SmallPolygons.cpp

結果

688.39pt 109th rating 1215 -> 1194 (-21)

ビジュアライザをC++で書き直して、提出するだけで終わってしまった。

ビジュアライザの交差判定をそのまま持ってきたらintオーバーフローしていて時間を食ってしまったりした。

最初の方針からしていまいちだったっぽい。

http://togetter.com/li/799735