1100 斜率最大(找规律)

1100 斜率最大 基准时间限制：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

/* 3个点A,B,C,把它们的按x坐标排序。假设排序后的顺序是ABC，那么有两种情况：其中k()表示求斜率。 1.ABC共线，则k(AB)=k(BC)=k(AC) 2.ABC不共线，则ABC将形成一个三角形，那么k(AC)<max(k(AB), k(BC)) 所以斜率最大的必然是挨在一起的两个点。 时间复杂度n*logn */ #include<cstdio> #include<iostream> #include<algorithm> using namespace std; struct node{ int x,y,id; bool operator<(node t)const { return x<t.x; } }point[10010]; int n; int main() { ios::sync_with_stdio(0); cin>>n; for(int i=0;i<n;i++) { cin>>point[i].x>>point[i].y; point[i].id=i; } sort(point,point+n); double ans=-99999999; int at; for(int i=1;i<n;i++) { double g=1.0*(point[i].y-point[i-1].y)/(point[i].x-point[i-1].x); if(ans<g) { ans=g; at=i; } } cout<<point[at-1].id+1<<" "<<point[at].id+1<<endl; return 0; }