Leetcode 1232 - Check If It Is a Straight Line

題目

Problem#

給你 n 個座標 coordinate[i] = (x, y)，問你能不能組成一條直線

測資限制#

• $2 \le n \le 1000$
• $-10^4 \le x, y \le 10^4$

想法#

• 怎麼檢查點 $a$、$b$ 和 $c$ 是否在同一直線上？

  • 計算 $(a, b)$ 和 $(b, c)$ 之間的斜率：如果 $s_ab = s_bc$，則它們在同一直線上。使用以下公式計算斜率：$s = \frac{y2 - y1}{x2 - x1}$。

• 時間複雜度: $\mathcal{O}(n\log{n})$

• 空間複雜度: $\mathcal{O}(1)$

AC Code#

• 步驟
  1. 按升序對點進行排序。
  2. 計算點 i 和 i+1 的斜率。
  3. 如果所有斜率的值都相同，則表示輸入是一條直線。

Copy

class Solution {
public:
    bool checkStraightLine(vector<vector<int>>& c) {
        int n = c.size();
 
        auto slope = [&](int i, int j) {
            double x1 = c[i][0], y1 = c[i][1];
            double x2 = c[j][0], y2 = c[j][1];
            return (y2-y1)/(x2-x1);
        };
 
        sort(c.begin(), c.end(), [](auto &lhs, auto &rhs) {
            return lhs[0] == rhs[0] ? lhs[1] < rhs[1] : lhs[0] < rhs[0];
        });
 
        double s = slope(0, 1);
        for(int i = 1; i < n-1; i++)
        {
            double tmp = slope(i, i+1);
            if(tmp != s)
            {
                return false;
            }
        }
        return true;
    }
};

view raw leetcode/1232.cpp delivered with ❤ by emgithub