筆試面試題目：三點共線的判斷

看膩了認知雞湯，你一無所獲，味同嚼蠟？看累了萬字長文，你收藏了事，心事重重？

那么，歡迎來到濤哥公眾號，我們一起，上點算法小菜，斟點程序小酒，品味一下短小的趣味算法和程序，別有一番風(fēng)味。

面試題目

在本文中，我們要討論的問題，小學(xué)生都可以看懂，卻出現(xiàn)在程序員的面試中，是我當(dāng)時應(yīng)聘一家游戲公司時遇到的問題，具體題目如下：

如何判斷三點共線？

多么簡單直白的題目，可要答好也并不容易。在面試時，我們要揚長避短，在自己熟悉的問題上，可以主動引導(dǎo)深入交流。

遇到多種方法時，可采取循序漸進、逐步優(yōu)化的方式進行介紹，這樣也能給面試官留下很好的印象：條理清晰、思路開闊、輕重合理、善于優(yōu)化。

這么簡單的題目，我們該如何著手呢？本文不是為了把答案給大家，而是跟大家一起，來探討處理問題的自然思路。

初中解法

最容易想到的，肯定是初中解法，即采用斜率的方式進行判斷，比如：

K(AB) = K(AC)

即AB的斜率等于AC的斜率。知道了A、B、C的坐標(biāo)，求斜率很簡單吧。然而，這個方法有個漏洞，因為當(dāng)AB垂直于X軸時，斜率不存在(無窮大)，所以，需要處理這種邊界情況。

高中解法

如果你連斜率都忘記了，那我挺無語的。但是，也別著急，用面積法也可以，如果三角形ABC的面積為0，則三點共線，即

S(ABC) = 0

那么，已知三點坐標(biāo)，如何計算三角形面試呢？顯然，海倫公式就可以搞定。只要高中不是特別貪玩，肯定用余弦定理證明過海倫公式，我來推導(dǎo)一下：

大學(xué)解法

如果你既忘記了斜率，又忘記了海倫公式，那我覺得是不太應(yīng)該的。估計三角形面積的行列式公式，也應(yīng)該也忘記了吧，如下：

注意：內(nèi)層黑色豎線是行列式，外層紅色豎線是絕對值。

小學(xué)解法

如果你忘記了上面的所有方法，那怎么辦呢。別多說了，這是在面試，還是要解決問題，那就現(xiàn)場來解決吧。

我們在小學(xué)就知道，兩點之間，直線段最短，所以，如果滿足如下條件之一，那也可以表明三點共線：

AB + BC = AC

AB + AC = BC

AC + BC = AB

這個是小學(xué)生就知道的方法，雖說是小學(xué)生解法，但求距離，還是要用初中知識的，說白了，就是勾股定理。

具體編程

搞清了算法之后，具體編程就很簡單了，我們以最后的一種方法為例，來寫個簡單程序吧：

#include <iostream>#include <cmath>using namespace std;
struct Point{  float x;  float y;};
float square(float x) {  return x * x;}
float getSide(const Point &p1, const Point &p2){  return sqrt( square(p1.x - p2.x) + square(p1.y - p2.y) );}
bool isEqual(float x, float y){  float z = x - y;  if (z > -0.000001 && z < 0.000001)  {    return true;  }    return false;}
bool isSameLine(const Point &A, const Point &B, const Point &C){  float AB = getSide(A, B);  float BC = getSide(B, C);  float AC = getSide(A, C);    if (isEqual(AB + AC, BC) || isEqual(AB + BC, AC) || isEqual(AC + BC, AB))  {    return true;  }    return false;}
int main(){  cout << isSameLine(Point{3, 3}, Point{4, 4}, Point{10, 10}) << endl;  cout << isSameLine(Point{3, 3}, Point{4, 4}, Point{10, 10.2}) << endl;  return 0;}

經(jīng)自測OK. 平時寫慣了golang, 再回來寫C++, 感覺總是容易漏掉分號，哎，也正常。

最后，希望大家在刷題中，有所進步，找到樂趣。祝找工作的朋友，拿到更好offer.  

答應(yīng)我，點個贊，點個在看，然后，也歡迎提出更好的思路，然后，早點去睡覺吧。

·················· END ··················

點擊關(guān)注公眾號，免費領(lǐng)學(xué)習(xí)資料

點“贊”和“在看”哦