将所有点按照横坐标排序之后,本题的核心就是判断任意相邻的三个点ABC是否共线。容易想到,我们判断线段AB和BC的斜率是否相等,即(y3-y2)/(x3-x2)==(y2-y1)/(x2-x1)
.这里可能会有两个问题,第一个就是精度,当两个小数非常接近时,浮点数很难判断准确。第二个就是当斜率是90度时,除数为0(此题中这个问题不存在)。
解决方案就是将除法转换为乘法,即判断(y3-y2)*(x2-x1)==(y2-y1)*(x3-x2)
即可。
相同的技巧在2152.Minimum-Number-of-Lines-to-Cover-Points
中也用到过。