O（n log n）時間内に特別な点kを見つけるアルゴリズム

Question

点の集合が特別な点kを持つかどうかをチェックするアルゴリズムの下限をn log n時間与えます。

Kは次のように定義される：A内の全ての点mに対して、kはそのような線分MQの中央にあるように点Qがある場合、点の集合Aの

akはAに属している必要はありません。

たとえば、このセットには、4つのポイント（1,0）、（0,1）、（0,1）、 1,1）、（0,0）である。

私がこの質問をしたとき、私は全くポーカーに直面していましたが、何も私の心には来なかった。私は幾分強い幾何学的背景が必要だと思う。

Answer 1

O(nlogn)ソリューション（あなたが下拘束ソリューションを探している、なぜ私はまだ明確ではないよ。あなたにもちょうど網羅チェックを行い、その後、ちょうど下限のを確認するためにnlognループを実行する可能性がありますあなたは上限を意味しなければならないと思います）：

すべてのポイントを平均して唯一の有効な候補ポイントを見つけます。私。それらの座標を合計し、点数で割ることによって計算される。そのようなkが存在する場合、これはそれです。そのようなkが存在しない場合、最後のステップで見つかったポイントが無効であることがわかります。

ポイントの新しい配列（集合）を作成します。ここでは、ポイントkの中心になるように軸をシフトします。私。 kは=（ _K X、Y _K）場合、点（x、y）は（Y-Y _K、X-X _K）となるであろう。比率x/yとノルムsqrt（x + y ）に従ってポイントをソートします。次のステップが示すように、このソートがどのように行われているかは重要ではなく、つまり、主な基準であり、副次的な基準です。

各点の補数を検索するか、またはそれよりも優れているだけで、配列をトラバースして2つの隣接する点がすべて補数であることを確認できます。私。これが解であれば、この新しい配列の2つの補完点はすべて、軸を元の位置に戻したので、（x、y）と（-x、-y）の形式になります。 ）とノルム、ソート後は隣接しなければなりません。

kが有効でない場合、このトラバーサルに到達するポイントがあり、その隣人が正しい/補完的なフォームではないことがわかります==>そのようなkはありません。確認するためのソートのために、それぞれの新しい点はOで算出することができるので、新しいアレイを構築するための候補K +
O(n)を求める

時間=
O(n)（1）+
O(nlogn) +
O(n)トラバーサル
= O(nlogn)

Answer 2

重心（最初に重複を削除したもの）を計算して、それがあなたのkであるかどうかを確認するといいでしょう。おそらく、それをO(n log n)にする唯一の事は、指定された場所でポイントを探し出すことでしょう。