5

http://www.glassdoor.com/Interview/Google-Interview-RVW2382108.htm

私はこの問題の解決策を見つけようとしました。しかし、私は成功していません..この問題をどのように進めるかについてのヒントを教えてください。

2点ずつ2組取ります。つまり、2つの和音を作ります。それらの垂直二等分線を見つけます。それらの二等分線を使用して、円の中心を見つけます...

さらに、円の方程式を導き出します。そして、点Mと円との交点を見つけてください...それが最も近い点になるはずです。ただし、その点は N 個の点の集合に存在する場合と存在しない場合があります。

ありがとう。

4

2 に答える 2

5

円の円周上のポイントが「順序どおり」(つまり、円の中心に対する角度でソートされている) であると仮定すると、角度ベースの二分探索を使用して、O(log(n))境界を達成することができます。

  1. A点Mから円の中心までの角度を計算します - O(1).
  2. 二分探索を使用して、円周上で最大角度が-Iより小さい点を見つけます。AO(log(n))
  3. 円は凸面なので、最も近い点MはIまたはI+1です。両方までの距離を計算し、最小値を取る - O(1).
于 2013-02-21T04:14:40.757 に答える
2

M に最も近い点を見つけるには、平面カットに基づいて点のバイナリ消去を行う必要があります。入力ポイントの少し前処理が必要です。その後、任意のポイント M に最も近いポイントを O(lgn) 時間で見つけることができます。

  1. (指定されていない場合) (r,θ) 形式で点の極座標表現を計算します。ここで、r は中心からの距離、θ は範囲 (-180,180] の x 軸からの角度です。
  2. X 軸からの角度の昇順ですべての N ポイントを並べ替えます。

ここでは、M に最も近い点の単純な二分探索は機能しないことに注意してください。

  • 与えられたポイントが θ = (-130,-100,-90,-23,-15,0,2,14,170) となるように並べ替えられている場合、θ = -170 のポイント M に対して、二分探索は -130 を返します。 (40 度離れた) が最も近いポイントであるのに対し、170 (20 度離れた) は M に最も近いポイントです。
  • 並べ替え中に符号を無視すると (正しい出力が生成されると考えて)、並べ替えられた新しい配列は θ = (0,2,14,15,23,90,100,130,170) のようになります。 6 の場合、結果は 2 または 14 のいずれかになりますが、この場合、0 は M に最も近い点です。

平面カットを使用して検索操作を実行するには、

  • 円の中心を通り、円の中心と点 M を結ぶ線に垂直な平面の切断線を見つけます。
  • 平面 M の半分に応じて、円形平面 [90+θ,-90+θ) または [-90+θ,90+θ) の半分を削除します。
  • 最初のカットに平行で、前の平面の中央の点を通過する平面カットを作成し、M から遠い平面の半分にあるすべての点を、平面の近くの半分に点がなくなるまで除去します。平面のほぼ半分を除去します。
  • 1 つの点が残るまで平面を切断し続けます。その点は M に最も近い点です。合計の操作には O(lgn) ステップかかります。

平面除去

データが歪んでおり、円内に均一に広がっていない場合は、各カットが検索操作で残されたポイントの中央値 (角度に基づく) を通過するように、平面カットを最適化できます。

于 2013-02-22T13:34:12.613 に答える