Pythonを使用して同じxまたはy座標を持つ最も近い点を見つけるプログラム

ptsと呼ばれる配列で与えられたポイントのセットがあると仮定します。現在の場所である別のポイント（x、y）もあります。有効なポイントを、現在のポイントと同じx座標または同じy座標を共有するポイントとして定義しています。現在の場所（x、y）からマンハッタン距離が最小の有効なポイントのインデックスを返す必要があります。複数のポイントがある場合は、インデックスが最小の有効なポイントを返します。 （注：2点（a、b）と（p、q）の間のマンハッタン距離は| a --p | + | b--q|です。

したがって、入力がpts =[（1,2）、（3,1）、（3,4）、（2,3）、（4,4）] pt =（2,4）のようである場合、最も近いポイント（3,4）と（2,3）が2つあるため、出力は2になりますが、（3,4）のインデックスは小さくなります。

これを解決するには、次の手順に従います-

• x、y：=pt

• idx：=-1

• 最小：=無限大

• ptsの各pについて、実行します

  • p [0]がxと同じであるか、p [1]がyと同じである場合、

    • dist：=| x --p [0] | + | y --p [1] |

    • 距離が<最小の場合

      • idx：=ptsのpのインデックス

      • 最小：=dist

    • それ以外の場合、distが最小と同じである場合、

      • pts

        • idx：=ptsのpのインデックス

        • 最小：=dist

• idxを返す

理解を深めるために、次の実装を見てみましょう-

例

def solve(pts, pt):
   x, y = pt
   idx = -1
   smallest = float("inf")
   for p in pts:
      if p[0] == x or p[1] == y:
         dist = abs(x - p[0]) + abs(y - p[1])
         if dist < smallest:
            idx = pts.index(p)
            smallest = dist
         elif dist == smallest:
            if pts.index(p) < idx:
               idx = pts.index(p)
               smallest = dist
   return idx
pts = [(1,2),(3,1),(3,4),(2,3),(4,4)]
pt = (2,4)
print(solve(pts, pt))

入力

[(1,2),(3,1),(3,4),(2,3),(4,4)], (2,4)

出力

2