【計算1】マンハッタン距離《新･Bランクup》

新・Bランクレベルアップメニュー 【計算 1】マンハッタン距離

問題【計算 1】マンハッタン距離
Task
点 P からのユークリッド距離とマンハッタン距離の 距離が近い 3 地点の番号を求めてね。

【計算 1】マンハッタン距離 コード 1/2 (C++実装例参照)

reader.on('close', () => {
   const [P_x, P_y] = lines[0].split(' ').map(Number);
   const N = Number(lines[1]);
   const Euclid = [];
   const Manhat = [];
   for (let i = 2; i < N + 2; i++) {
      const [F_x, F_y] = lines[i].split(' ').map(Number);
      const E = Math.sqrt((P_x - F_x) ** 2 + (P_y - F_y) ** 2);
      const M = Math.abs(P_x - F_x) + Math.abs(P_y - F_y);
      Euclid.push([i - 1, E]);
      Manhat.push([i - 1, M]);
   }
   closest(Euclid);
   closest(Manhat);

   function closest(distance) {
      distance.sort((s, b) => s[1] - b[1]);
      for (let i = 0; i < 3; i++) {
         console.log(distance[i][0]);
      }
   }
});
hogeちゃんの画像

ユークリッド距離(P_1, P_2) = sqrt((x_1 – x_2) ^ 2 + (y_1 – y_2) ^ 2)
マンハッタン距離(P_1, P_2) = | x_1 – x_2 | + | y_1 – y_2 |

sqrt → 平方根

| value | → value の絶対値

top

【計算 1】マンハッタン距離 コード 2/2 (C++実装例参照)

reader.on('close', () => {
   const [px, py] = lines[0].split(' ').map(Number);
   const N = Number(lines[1]);
   const euclid_len = [];
   const taxi_len = [];
   for (let i = 2; i < N + 2; i++) {
      const [x, y] = lines[i].split(' ').map(Number);
      euclid_len.push([Math.sqrt((px - x) ** 2 + (py - y) ** 2), i - 1]);
      taxi_len.push([Math.abs(px - x) + Math.abs(py - y), i - 1]);
         }
   euclid_len.sort((s, b) => s[0] - b[0]);
   taxi_len.sort((s, b) => s[0] - b[0]);
   for (let i = 0; i < 3; i++) {
      console.log(euclid_len[i][1]);
   }
   for (let i = 0; i < 3; i++) {
      console.log(taxi_len[i][1]);
   }
});
hogeちゃんの画像

実装例 C++の場合を参照。

top

コメント