基准时间限制：1 秒 空间限制：131072 KB 分值: 20 难度：3级算法题
平面上有N个点，任意2个点确定一条直线，求出所有这些直线中，斜率最大的那条直线所通过的两个点。
（点的编号为1-N，如果有多条直线斜率相等，则输出所有结果，按照点的X轴坐标排序，正序输出。数据中所有点的X轴坐标均不相等，且点坐标为随机。）
Input
第1行，一个数N，N为点的数量。(2 <= N <= 10000)
第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示例
4 2
一次过，开心。
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct point
{
int x,y;int id;
bool operator<(point &p2)
{
if(x!=p2.x)return x<p2.x;
else return y<p2.y;
}
} P[10005];
queue<pair<int,int> >q;
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
#endif // ONLINE_JUDGE
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d%d",&P[i].x,&P[i].y);
P[i].id=i;
}
sort(P+1,P+n+1);
point tmp=P[1];int id=1;
ll maxk1=0;ll maxk2=666;
ll t1,t2;
for(int i=2;i<=n;i++)
{
if(P[i].y<=tmp.y)tmp=P[i],id=P[i].id;
else if(P[i].x!=tmp.x)
{
t1=P[i].y-tmp.y;
t2=P[i].x-tmp.x;
if(t1*maxk2>t2*maxk1)
{
while(!q.empty())q.pop();
q.push(make_pair(id,P[i].id));
maxk1=t1,maxk2=t2;
}
else if(t1*maxk2==t2*maxk1)
{
q.push(make_pair(id,P[i].id));
}
else tmp=P[i],id=P[i].id;
}
}
while(!q.empty())
{
cout<<q.front().first<<" "<<q.front().second<<endl;
q.pop();
}
return 0;
}