部外者をはじけ

今回は paiza の「部外者をはじけ」の問題に挑戦！

問題概要

🧩 入力

• 1行目：人数 N
• 続く N 行：各人物の座標 (x_i, y_i)

🔍 求めるもの

• ある直線を引いた際に最も部外者が少なくなるような直線を、列に対する「正しい直線」とする。

• 部外者とは直線から 2 m以上離れた人。

• 正しい直線を引いたとき部外者として検出された人物を求める

📤 出力

• 部外者の番号（1始まり） を昇順で出力
• 部外者がいない場合 は none を出力

入力例:

4
10.0 20.0
340.0 235.0
20.0 40.0
30.0 60.0

出力例:

2

✅OK例：

const rl = require('readline').createInterface({ input: process.stdin });

const lines = [];
rl.on('line', (input) => lines.push(input));
rl.on('close', () => {
  const N = Number(lines[0]);
  const points = lines.slice(1).map(line => line.split(' ').map(Number));

  let bestA = 0, bestB = 0, bestC = 0;
  let minOutliers = Infinity;

  // すべての「異なる2点のペア」を試す
  for (let i = 0; i < N - 1; i++) {
    for (let j = i + 1; j < N; j++) {
      const [x1, y1] = points[i];
      const [x2, y2] = points[j];

      // 2点を通る直線の一般形 ax + by + c = 0
      const a = y2 - y1;
      const b = -(x2 - x1);
      const c = (x2 - x1) * y1 - (y2 - y1) * x1;

      // 各点との距離を計算して「部外者の数」を数える
      let count = 0;
      for (let k = 0; k < N; k++) {
        const [x, y] = points[k];
        const d = Math.abs(a * x + b * y + c) / Math.sqrt(a ** 2 + b ** 2);
        if (d >= 2) count++;  // 2m以上離れていたら部外者
      }

      // 部外者が最も少ない直線を記録
      if (count < minOutliers) {
        minOutliers = count;
        bestA = a;
        bestB = b;
        bestC = c;
      }
    }
  }

  // 部外者がいない場合
  if (minOutliers === 0) {
    console.log('none');
    return;
  }

  // 最良の直線に基づいて部外者を出力
  for (let i = 0; i < N; i++) {
    const [x, y] = points[i];
    const d = Math.abs(bestA * x + bestB * y + bestC) / Math.sqrt(bestA ** 2 + bestB ** 2);
    if (d >= 2) console.log(i + 1);
  }
});

🧭 処理の流れ

1. 入力を受け取る
   • 1行目：人数 N
   • 2行目以降：各人の座標 (x, y)
     → 配列 points に格納
2. 変数を初期化
   • bestA, bestB, bestC：最も良い直線の係数
   • minOutliers：部外者の最小数（初期値はInfinity）
3. すべてのペアの2点を組み合わせて試す
   • for (i) と for (j) の二重ループで全組合せ
   • それぞれのペア (x1, y1) と (x2, y2) から直線を求める
4. 2点を通る直線の方程式を求める
   • 一般形 ax + by + c = 0 に変換
   • a = y2 - y1
   • b = -(x2 - x1)
   • c = (x2 - x1) * y1 - (y2 - y1) * x1
5. 全員との距離を計算して、部外者を数える
   • 各点 (x, y) に対し
   • d = |a*x + b*y + c| / √(a² + b²)
   • d >= 2 なら部外者とみなしてカウント
6. 最も部外者が少ない直線を記録する
   • count < minOutliers のとき、
     → この直線を「仮の最良」として更新
7. すべてのペアを試し終えたら
   • 最も部外者が少ない直線の a, b, c が確定
8. 部外者がいなければ "none" を出力して終了
9. 部外者がいる場合は番号を出力
   • 各点との距離を再計算し、d >= 2 の人だけ i+1（番号）を出力

📝まとめ

🔹「全員の中から2人を選んで直線を作る」
🔹「その直線に対して2m以上離れている人数を数える」
🔹「部外者が最も少ない直線を選ぶ」
🔹「その直線から2m以上離れた人（部外者）を出力する」

僕の失敗談(´;ω;｀)と解決法🐈