如何证明共线（看看大佬怎么刷题的）

看腻了认知鸡汤，你一无所获，味同嚼蜡？看累了万字长文，你收藏了事，心事重重？

那么，欢迎来到涛哥公众号，我们一起，上点算法小菜，斟点程序小酒，品味一下短小的趣味算法和程序，别有一番风味。

面试题目

在本文中，我们要讨论的问题，小学生都可以看懂，却出现在程序员的面试中，是我当时应聘一家游戏公司时遇到的问题，具体题目如下：

如何判断三点共线？

多么简单直白的题目，可要答好也并不容易。在面试时，我们要扬长避短，在自己熟悉的问题上，可以主动引导深入交流。

遇到多种方法时，可采取循序渐进、逐步优化的方式进行介绍，这样也能给面试官留下很好的印象：条理清晰、思路开阔、轻重合理、善于优化。

这么简单的题目，我们该如何着手呢？本文不是为了把答案给大家，而是跟大家一起，来探讨处理问题的自然思路。

初中解法

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

K(AB) = K(AC)

即AB的斜率等于AC的斜率。知道了A、B、C的坐标，求斜率很简单吧。然而，这个方法有个漏洞，因为当AB垂直于X轴时，斜率不存在(无穷大)，所以，需要处理这种边界情况。

高中解法

如果你连斜率都忘记了，那我挺无语的。但是，也别着急，用面积法也可以，如果三角形ABC的面积为0，则三点共线，即

S(ABC) = 0

那么，已知三点坐标，如何计算三角形面试呢？显然，海伦公式就可以搞定。只要高中不是特别贪玩，肯定用余弦定理证明过海伦公式，我来推导一下：

大学解法

如果你既忘记了斜率，又忘记了海伦公式，那我觉得是不太应该的。估计三角形面积的行列式公式，也应该也忘记了吧，如下：

注意：内层黑色竖线是行列式，外层红色竖线是绝对值。

小学解法

如果你忘记了上面的所有方法，那怎么办呢。别多说了，这是在面试，还是要解决问题，那就现场来解决吧。

我们在小学就知道，两点之间，直线段最短，所以，如果满足如下条件之一，那也可以表明三点共线：

AB + BC = AC

AB + AC = BC

AC + BC = AB

这个是小学生就知道的方法，虽说是小学生解法，但求距离，还是要用初中知识的，说白了，就是勾股定理。

具体编程

搞清了算法之后，具体编程就很简单了，我们以最后的一种方法为例，来写个简单程序吧：

#include 
#include 
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;
}

经自测OK. 平时写惯了golang, 再回来写C++, 感觉总是容易漏掉分号，哎，也正常。