平面上N个点,每两个点都确定一条直线, 求出斜率最大的那条直线所通过的两个点

时间:2021-10-30 14:38:47
平面上N个点,每两个点都确定一条直线,

求出斜率最大的那条直线所通过的两个点(斜率不存在的情况不考虑)。时间效率越高越好。


平面上N个点,每两个点都确定一条直线,求出斜率最大的那条直线所通过的两个点(斜率不存在的情况不考虑)。时间效率越高越好。
关于这道题,网上已经给出了解答要点:
3个点A,B,C,把它们的按x坐标排序。假设排序后的顺序是ABC,那么有两种情况:
1.ABC共线,则k(AB)=k(BC)=k(AC)
2.ABC不共线,则ABC将形成一个三角形,那么k(AC)<max(k(AB), k(BC))
其中k()表示求斜率。
所以程序的基本步骤就是:
1.N个点按x坐标排序。
2.遍历,求相邻的两个点的斜率,找最大值。
时间复杂度Nlog(N)

 

先把这些点按x坐标从小到大排序,斜率最大的两点必然是挨一起的两个点,所以排序O(n* lg n),遍历一次O(n)就够了