ECNU机试之求最大斜率的两点

平面上有N个点，任意2个点确定一条直线，求出所有这些直线中，斜率最大的那条直线所通过的两个点。（点的编号为1-N，如果有多条直线斜率相等，则输出所有结果，按照点的X轴坐标排序，正序输出。数据中所有点的X轴坐标均不相等）

Input

第1行，一个数N，N为点的数量。(2 <= N <= 50)

第2 - N + 1行：具体N个点的坐标，X Y均为整数(-10^9 <= X,Y <= 10^9)

Output

每行2个数，中间用空格分隔。分别是起点编号和终点编号（起点的X轴坐标<终点的X轴坐标）

Input示例

5
1 2
6 8
4 4
5 4
2 3

Output示例

5 4
6 8

解题思想：将这些坐标点按横坐标排序，求相邻两点的斜率，找出最大斜率后输出直线两点。

参考代码（没有用STL）：

#include <iostream>

using std::cin;
using std::cout;
using std::endl;

struct node //存储点的信息
{
    float x,y;
};

int main()
{
    int n=0;
    while(cin>>n)
    {
        node nodes[50];
        float k[50];
        for(int i=0; i<n; i++)
        {
            cin>>nodes[i].x>>nodes[i].y;
        }

        for(int i=n; i>0; i--)
        {
            for(int i=0; i+1<n; i++)
            {
                if(nodes[i].x>nodes[i+1].x)
                {
                    node temp;
                    temp=nodes[i];
                    nodes[i]=nodes[i+1];
                    nodes[i+1]=temp;
                }
            }
        }
        for(int i=0; i+1<n; i++)//求两点之间斜率
        {
            if((nodes[i+1].x-nodes[i].x)==0)//除0
            {
                k[i]=99999;
                continue;
            }
            k[i]=(nodes[i+1].y-nodes[i].y)/(nodes[i+1].x-nodes[i].x);
            cout<<k[i]<<endl;
        }

        float max_a=k[0];
        for(int i=0; i<n-1; i++) //找出最大斜率
        {
            if(max_a<k[i])
            {
                max_a=k[i];
            }
        }

        for(int i=0; i<n; i++)
        {
            if(k[i]==max_a)
            {
                cout<<nodes[i].x<<" "<<nodes[i].y<<endl;//输出结点
                cout<<nodes[i+1].x<<" "<<nodes[i+1].y<<endl;
            }
        }
    }
    return 0;
}