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

解法一：二重循环，算法复杂度O(n2)。

int GetMaxSlope(vector<Point> &points, int &i, int &j)
{
if (points.empty() || points.size()==1)
{
i = -1;
j = -1;
return -1;
}

if (points.size()==2)
{
i = 0;
j = 1;
return 0;
}

double fCurSlope = 0;
double fMaxSlope = (points[0].y - points[1].y) / (points[0].x - points[1].x);

i = 0;
j = 1;

for (vector<Point>::size_type k = 0; k != points.size(); k++)
{
for (vector<Point>::size_type m = 0; m != points.size(); m++)
{
if (k == m)
continue;

fCurSlope = (points[k].y - points[m].y) / (points[k].x - points[m].x);
if (fMaxSlope < fCurSlope)
{
fMaxSlope = fCurSlope;
i = k;
j = m;
}
}
}

return 0;
}

解法二：如果对这组点按横坐标排序，会有如下规律（以3个点的情况为例）：

A、B、C 3个点，已按横坐标排序，则：

1. ABC共线，则k(AB)=k(BC)=k(AC)；

2. ABC不共线，则ABC将形成一个三角形，那么k(AC)<max(k(AB), k(BC))

算法复杂度O(nlogn)。

int GetMaxSlope(vector<Point> &points, int &i, int &j)
{
if (points.empty() || points.size()==1)
{
i = -1;
j = -1;
return -1;
}

if (points.size()==2)
{
i = 0;
j = 1;
return 0;
}

std::sort(points.begin(), points.end());

double fCurSlope = 0;
double fMaxSlope = (points[0].y - points[1].y) / (points[0].x - points[1].x);

i = 0;
j = 1;


for (vector<Point>::size_type k = 2; k != points.size(); k++)
{
fCurSlope = (points[k-1].y - points[k].y) / (points[k-1].x - points[k].x);
if (fMaxSlope < fCurSlope)
{
fMaxSlope = fCurSlope;
i = k-1;
j = k;
}
}
return 0;
}