この問題は、いくつか格子点が与えられるので、その格子点の中からいくつか選んで単純多角形を作り、その内部(線上はナシ)に原点を取り囲め、というものです。
まず、少し頭を使って考えると、下図のように、ある3点を結ぶ三角形の内部に原点が来る場合、もしくはある2点を結ぶ線上に原点が来てその線を対角線とする四角形の内部に原点が来る場合の2通りしかないことがわかります。(雑に言うと、五角形以上が冗長であることを意味します。)
次に、それぞれの場合についてありうる場合を全探索し、面積の最小を求めます。
ここで、ベクトルの外積が大活躍します。ここの記事内では外積は
とします。外積について詳しくは
などを参照してみてください。(今回の記事内では、外積という三次元のベクトル量を、z成分だけ取り出してあたかもスカラー量として扱うことをお許しください)
まず、三角形の内部に原点を含む場合。
次にある2点を結ぶ線上に原点が来てその線を対角線とする四角形の内部に原点が来る場合。
あとは、三角形の場合の3点と、四角形の場合の対角線の2点+おまけでつける2点を全探索すればです。
Submission #4078441 - 東京工業大学プログラミングコンテスト2015
外積を扱えるとこんな感じでかなり楽に解けちゃいます。幾何人権を目指したいならマスターしておくとよいでしょう。(僕が幾何人権であるとは言ってない)
