缀点成线(Check If It Is a Straight Line)

在一个 XY 坐标系中有一些点，我们用数组 coordinates 来分别记录它们的坐标，其中 coordinates[i] = [x, y] 表示横坐标为 x、纵坐标为 y 的点。

请你来判断，这些点是否在该坐标系中属于同一条直线上，是则返回 true，否则请返回 false。

示例 1： 图裂了

输入：coordinates = [[1,2],[2,3],[3,4],[4,5],[5,6],[6,7]]
输出：true

示例 2： 图裂了

输入：coordinates = [[1,1],[2,2],[3,4],[4,5],[5,6],[7,7]]
输出：false

提示：

  • 2 <= coordinates.length <= 1000
  • coordinates[i].length == 2
  • -10^4 <= coordinates[i][0], coordinates[i][1] <= 10^4
  • coordinates 中不含重复的点
bool checkStraightLine(int** coordinates, int coordinatesSize, int* coordinatesColSize){
    for (int i = 0; i < coordinatesSize; ++i) {
        for (int j = i+1; j < coordinatesSize; ++j) {
            for (int k = j+1; k < coordinatesSize; ++k) {
                int x1 = coordinates[i][0];
                int y1 = coordinates[i][1];
                int x2 = coordinates[j][0];
                int y2 = coordinates[j][1];
                int x3 = coordinates[k][0];
                int y3 = coordinates[k][1];
                if ((y2-y1)*(x3-x1) != (y3-y1)*(x2-x1)){
                    return false;
                }
            }
        }
    }
    return true;
}

最简单粗暴的写法，注意不要用斜率相等，因为有可能分母为0，而且用整数除法得到的还是除法，用乘法比除法好

  1. 浮点数比较相等会有误差，不如整数乘整数
  2. 不用强制类型转换
  3. 不用为分母是否为0去特殊处理
bool checkStraightLine(int** coordinates, int coordinatesSize, int* coordinatesColSize){
    int x1 = coordinates[0][0];
    int y1 = coordinates[0][1];
    int x2 = coordinates[1][0];
    int y2 = coordinates[1][1];
    int dx = x2-x1;
    int dy = y2-y1;

    for (int i = 2; i < coordinatesSize; i++) {
        int x3 = coordinates[i][0];
        int y3 = coordinates[i][1];

        if (dy*(x3-x1) != (y3-y1)*dx) {
            return false;
        }
    }
    return true;
}

超级提速，从 O(n^3) 到 O(n)