「ハッピーエンド問題」と呼ばれる数学の未解決問題に関連したプログラムを書いてみましょう。平面上に与えられたN個の点から、ちょうどk個の点を結んでできる凸多角形のうち、最も面積の小さいものを見つけるプログラムを作成してください。ただし、N個の点の座標を与えられた後、質問として凸多角形の角の個数kがいくつか与えられます。
（補足：ハッピーエンド問題について）
平面上にどの３点も同じ直線上に乗らないようにN個の点を置きます。そのとき、どのように点を置いても、k個の点をうまく選ぶとk個の角をもつ凸多角形が必ず作れると予想されています。 今のところ、三角形ならばN=3、四角形ならばN=5、五角形ならばN=9、六角形ならばN=17であればよいことが、２００６年までに証明されています。また、三角形以上のすべてのk角形に対して、N=1+2k-2という予想がありますが、いまだ証明されていません。これは１００年にわたり研究が進められている難問です。
この問題には、「ハッピーエンド問題」という素敵な名前がつけられています。ある男女がこの問題を研究しているうちに仲良くなって、ついに結婚したことにちなんで、友人の数学者が名付けたそうです。ロマンチックですね。
入力は1つのデータセットからなる。入力データは以下の形式で与えられる。
N x1 y1 : xN yN Q k1 : kQ
１行目に平面上の点の個数N(3 ≤ N ≤ 40)が与えられる。続くN行に各点の座標が与えられる。各点には1からNまでの番号が、入力される順番に付けられている。xiとyi(-10000 ≤ xi, yi ≤ 10000)はi番目の点のそれぞれx座標とy座標を表す整数である。x軸の正方向は右向き, y軸の正方向は上向きに取るものとする。
続く１行に質問の数Q(1 ≤ Q ≤ N)が与えられる。続くQ行に質問が与えられる。ki(3 ≤ ki ≤ N)はi番目の質問である凸多角形の角の個数を表す。
なお、入力は以下の条件を満たすものとする。
質問ごとに、面積が最小の凸多角形の全頂点を1行に出力する。凸多角形の頂点で最も下にあるものの中で最も左にある頂点から順に、反時計周りで頂点の番号を出力する。頂点の番号の間は空白1つで区切る。行の終わりには空白文字を出力しない。ただし、凸多角形が作れない場合はNAと出力する。
5 0 0 3 0 5 2 1 4 0 3 3 3 4 5
1 4 5 1 2 4 5 1 2 3 4 5
6 0 0 3 0 5 2 1 4 0 3 3 2 4 3 4 5 6
6 3 5 6 3 4 5 1 2 6 4 5 NA