Cho n điểm trên mặt phẳng 2D, hãy kiểm tra xem mọi điểm có nằm trên cùng một đường thẳng hay không.

Bài học kỹ thuật. Đây là một trong những bài "dễ" mà phép toán thì đúng nhưng máy tính lại không. JavaScript lưu số dưới dạng IEEE-754 (double), và phép chia hiếm khi chính xác tuyệt đối. Khi một hệ thống thực tế phụ thuộc vào hình học — bản đồ, công cụ vẽ, kiểm tra va chạm — cách tính slope ngây thơ sẽ sớm thất bại với các trường hợp biên. Cách sửa kinh điển: tránh phép chia hoàn toàn, dùng phép nhân chéo (cross-multiplication) thay thế.

Ý tưởng

Mọi đường thẳng đều có thể viết dưới dạng x = ay + b, trong đó (x, y) là điểm thuộc đường thẳng. Nếu xác định được a và b từ hai điểm đã biết, ta có thể kiểm tra mọi điểm còn lại với cùng phương trình.

Lấy hai điểm (x, y) và (x', y'):

x = ay + b
x' = ay' + b

Trừ hai phương trình cho nhau: x - x' = (y - y')a, suy ra a = (x - x') / (y - y') và b = x - ay.

Nghe sạch sẽ — vậy hãy code thử.

Lời giải ngây thơ (và nơi nó thất bại)

function checkStraightLine(coordinates: number[][]): boolean {
  const [deltaX, deltaY] = [
    coordinates[0][0] - coordinates[1][0],
    coordinates[0][1] - coordinates[1][1],
  ];
  const a = deltaX / deltaY;
  const b = coordinates[0][0] - a * coordinates[0][1];
 
  for (let i = 2; i < coordinates.length; i++) {
    if (deltaX === 0) {
      if (coordinates[i][0] !== coordinates[i - 1][0]) return false;
    } else if (deltaY === 0) {
      if (coordinates[i][1] !== coordinates[i - 1][1]) return false;
    } else if (coordinates[i][0] !== a * coordinates[i][1] + b) {
      return false;
    }
  }
 
  return true;
}

Đoạn này vượt qua 63/80 test case, rồi thất bại ở case 64:

[[8,78],[2,18],[-1,-12],[-5,-52],[-4,-42],[-8,-82],[3,28],[9,88]]

Tính tay xem:

deltaX = 8 - 2 = 6
deltaY = 78 - 18 = 60
a = deltaX / deltaY = 6 / 60 = 0.1
b = x - ay = 8 - 0.1 * 78 = 0.2

Thêm console.log(a, b) vào, kết quả là:

0.1 0.1999999999999993

Đây rồi: lỗi dấu phẩy động. 6 / 60 không chính xác bằng 0.1 trong hệ nhị phân, và sai số nhỏ lan truyền vào b. Mọi phép so sánh với đường thẳng giờ lệch đi vài e-16, và một điểm rơi vào bên sai của phép kiểm tra !==. (Hoặc, như tôi thường nói đùa, đổi sang C++ hay Java — nhưng chỉ khi thực sự bắt buộc.)

Cách sửa: nhân chéo

Thực ra chúng ta không cần slope. Quay lại suy luận hai điểm:

x = ay + b      x' = ay' + b      x'' = ay'' + b

Trừ vế cho nhau được hai tỉ lệ, và thay vì chia, ta nhân chéo:

(x - x')(y - y'') = (y - y')(x - x'')

Đẳng thức này chỉ dùng phép trừ và phép nhân — cả hai đều chính xác với số nguyên, và miễn nhiễm với bẫy số thực.

function checkStraightLine(coordinates: number[][]): boolean {
  const [deltaX, deltaY] = [
    coordinates[0][0] - coordinates[1][0],
    coordinates[0][1] - coordinates[1][1],
  ];
 
  for (let i = 2; i < coordinates.length; i++) {
    const [deltaX2, deltaY2] = [
      coordinates[i][0] - coordinates[0][0],
      coordinates[i][1] - coordinates[0][1],
    ];
 
    if (deltaX * deltaY2 !== deltaY * deltaX2) {
      return false;
    }
  }
 
  return true;
}

Không phép chia, không 0.1, không 0.1999999999999993. Chỉ một bất biến hình học sạch sẽ.

Độ phức tạp

  • Thời gian: O(n) — duyệt một lần qua các điểm.
  • Bộ nhớ: O(1) — một hằng số biến.

Bài học

Mỗi khi bạn định chia trong một phép kiểm tra đẳng thức, hãy tự hỏi: nhân chéo được không? Số thực là kẻ giết người thầm lặng — phép toán đúng, đáp án sai, và test bắt được nó nằm ở case 64/80. Trong sản phẩm thực, hãy ưu tiên số học chính xác với số nguyên cho các phép so sánh khi bài toán cho phép.