円卓の騎士と長方形

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

TSP-Traveling gas Statoin Problem(巡回ガソリンスタンド問題)

環状の道路に,N軒のガソリンスタンドが時計回りに1からNまで番号づけられて並んでいる.燃料タンクが空の状態から出発し,途中でガソリンが不足することなく車でこの環状道路を時計回りに一周したい.ガソリンスタンドiではp_iリットルのガソリンが補給される.ガソリンスタンドiから次のガソリンスタンドまで移動するのにq_iリットルのガソリンを消費する.ここで