三角形を形成する 2D の点のセットが与えられる小さなコンテストの問題があります。この三角形は、任意の回転、任意の並進 (両方とも 2D 平面内) の影響を受ける可能性があり、ミラーでの反射の影響を受ける可能性がありますが、その寸法は変更されていません。次に、それらは平面内の一連の点を与えてくれます。これらの幾何学的操作を 1 つ以上実行した後、三角形を形成する 3 つの点を見つける必要があります。
例：
5 15
8 5
20 10
6
5 17
5 20
20 5
10 5
15 20
15 10
Output:
5 17
10 5
15 20
既知のアルゴリズムを適用することになっているに違いありませんが、どれかはわかりません。最も一般的なものは、凸包、スイープ平面、三角形分割などです。
誰かがヒントを与えることができますか？コードは必要ありません。プッシュのみでお願いします。
三角形は、その3つの辺の長さによって一意に定義されます（回転、反転、および平行移動は無視されます）。元の三角形A、B、Cの頂点にラベルを付けます。| AB |のようなポイントD、E、Fを探しています = | DE |、| AC | = | DF |、および| BC | = |EF|。長さはピタゴラスの式で与えられます（ただし、線分の長さの2乗を比較することで、各テストで平方根演算を保存できます...）
与えられた三角形は、3 つの長さによって定義されます。これらの長さで区切られたリスト内の 3 つのポイントを検索します。
に煩わされないように、指定された長さを 2 乗しsqrtます。
リスト内のすべての点のペア間の距離の 2 乗を求め、指定された長さ (O(V^2)) と一致するものだけに注目しますが、ほとんどの長さが一致しないため、係数は低くなります。
これで、O(V) エッジを持つスパース グラフができました。O(V) 時間でサイズ 3 のすべてのサイクルを見つけ、一致を切り詰めます。(最善の方法はわかりませんが、適切な big-O を使用した方法の 1 つを次に示します。)
全体の複雑さ: O(V^2) ただし、ポイントの数によっては、O(V) でサイクルを見つけることが制限要因になる場合があります。ポイントのリストを空間的に並べ替えて、すべてのペアを見ないようにすると、漸近的な動作が改善されます。
これは通常、行列演算で行われます。 このウィキペディアの記事では、回転、平行移動、反射行列について説明しています。別のサイトはこちら（写真あり）。
変換は単に回転、スケーリング、ミラーリングであるため、三角形の 2 辺の内積をチェックすることで、変換された三角形を形成する点を見つけることができます。
これは、AB.AC = |AB| であるため機能します。x |AC| x cos(a)、および 2 つの長さとそれらの間の角度が三角形を定義します。
編集: はい、ジムの言うとおりです。内積は 1 つだけでは不十分です。ED.EF と FD.FE を含む 3 つすべてを行う必要があります。したがって、最終的には、平方距離法と同じ数の計算が行われます。