Skip to content

Latest commit

 

History

History

2280.Minimum-Lines-to-Represent-a-Line-Chart

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
 
 
 
 

2280.Minimum-Lines-to-Represent-a-Line-Chart

将所有点按照横坐标排序之后,本题的核心就是判断任意相邻的三个点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中也用到过。