プログラミング・コンテスト

http://azspcs.com/contest/polygonalareas
なかなか奥が深い問題です。N*Nのグリッド上にN個の点を置いて順に結び多角形を作ります。以下の三つの条件を満たすこと:

  • X,Y座標ともに重複がない
  • どの辺も交差しない
  • どの辺も平行でない

この条件の元で面積がなるべく小さいものと大きいものを見つけた人の勝ち。
整数の足し算、掛け算だけで辺の平行、交差の判定や面積の計算を行うとか、O(N)の計算時間にするとか、なかなか高度な技術を要求されます。
そんなん楽勝やん、という人は是非挑戦を。登録しなくても Best scoreは見られるので計算結果がどの程度いい線いってるかは分かります。
最大サイズでも全てキャッシュに乗るサイズなんで純粋に計算の速さが効いてきます。