円卓の騎士と長方形

円周上にN個の点があるとする(N≧4)．その中の一つの点から始めて，時計回りに順にとする．円の中心を原点とする正規直交座標系における各点の座標がいずれも有理数であって，これらが与えられているものとする．次のそれぞれの問題に対して，N に関して線形時間のアルゴリズムを設計せよ．ただし，有理数同士の加減乗除および大小比較は単位時間で実行できるものとする．

(1)の中に円の直径の両端点となる２点が存在するかどうかを判定する問題．

(2)の中の４点を頂点とする長方形が存在するかどうかを判定する問題．

(3)の中の４点を頂点とする長方形の中で面積が最大となるものを求める問題．

なんか編集途中で、内容が破棄されてやる気なくなかったら、これは問題だけ。気が向いたら続きを書く。(たぶん書かない）