1

次の問題に対して、実行時間O（nlogn）のアルゴリズムを設計する必要があります。

n個の点のセットPが与えられた場合、せん断変換（x、y）->（x + Ay、y）がx座標が等しくない点の順序（x方向）を変更しないように、値A>0を決定します。 。

どこから始めればいいのかわからなくても大変です。

これに関する助けをいただければ幸いです。

ありがとうございました！

4

3 に答える 3

0

私はy=0だと思います。

When x = 0, A > 0
(x,y) -> (x+Ay,y)
      -> (0+(A*0),0) = (0,0)
When x = 1, A > 0
(x,y) -> (x+Ay,y)
      -> (1+(A*0),0) = (1,0)

x座標が等しくない、(2,0)、(3,0)、(4,0)...なので、始点は(0,0)、x=0でよいと思います。

于 2011-11-15T02:51:54.717 に答える
0

わかりました、ここでメソッドを大まかに突き刺します。

ポイントのリストを x 順で並べ替えます。(これにより O(nlogn) が得られます。これ以降のすべてのステップは O(n) です。)

x 座標間の差 dx_i = x_(i+1) - x_i の新しいリストを生成します。x_i が順序付けられているため、これらの dx_i はすべて >= 0 です。

ある A の場合、変換された dx_i(A) は x_(i+1) -x_i + A * ( y_(i+1) - y_i) になります。これが負またはゼロの場合 (x_(i+1)(A) < x_i(A))、次数が変更されます。

したがって、各 dx_i について、dx_i(A) をゼロにする A の値、つまり A_i = - (x_(i+1) - x_i)/(y_(i+1) - y_i) を見つけます。これで、連続する (x オーダーの) ペアのポイント間でオーダー スワップを「引き起こす」係数のリストができました。ゼロ除算に注意してください。ただし、2 つの点の y が同じ場合は、これらの点の順序は変わりません。A_i の一部は負になるため、A>0 の場合はこれらを破棄します。(負の A_i もオーダー スワップを誘発するため、A>0 の要件は少し恣意的です。)

リストで最小の A_i > 0 を見つけます。したがって、0 < A < A_i(min) の A は、ポイントの順序を変更しないせん断になります。A_i(min) を選択すると、2 つの点が同じ x に移動しますが、互いに通り過ぎません。

于 2011-11-15T03:11:32.530 に答える
0

すべての x、y 座標が正の数であるとします。(一般性を失うことなく、オフセットを追加できます。) 時間 O(n log n) で、ポイントのリスト L を、主に x 座標の昇順で、次に y 座標の昇順で並べ替えます。時間 O(n) で、点のペアを (L の順序で) 次のように処理します。p、q を L 内の任意の 2 つの連続する点とし、px、qx、py、qy をそれらの x および y 座標値とする。そこから、いくつかのケースを検討する必要があるだけで、何をすべきかは明らかです。px=qx の場合、何もしません。それ以外の場合、py<=qy の場合は何もしません。Else (px>qx, py>qy) の場合、px + A*py < qx + A*qy、つまり(px-qx)/(py-qy) > Aが必要です。

したがって、L を順番に調べて、px>qx および py>qy であるすべての点のペアで満たされる最大の A' を見つけます。次に、A' より少し小さい A の値、たとえば A'/2 を選択します。(または、問題の目的がそのような最大の A を見つけることである場合は、単に A' 値を報告します。)

于 2011-11-15T02:57:26.207 に答える