【51nod 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

思路：先按照x进行排序，然后最大的斜率肯定是相邻的两个点，直接遍历一遍即可。

#include<iostream> #include<algorithm> using namespace std; #define MAXN 10005 typedef long long ll; struct poll { ll x,y; ll flag; ll num; } s[MAXN]; bool cmp(poll a,poll b) { return a.x<b.x; } int main() { ll n; cin>>n; for(ll i=0;i<n;i++) { cin>>s[i].x>>s[i].y; s[i].num=i+1; } sort(s,s+n,cmp); ll maxx=-0x3f3f3f3f; ll k; for(ll i=0;i<n-1;i++) { k=(s[i+1].y-s[i].y)/(s[i+1].x-s[i].x); if(k>maxx) { maxx=k; } } for(ll i=0;i<n-1;i++) { if((s[i+1].y-s[i].y)/(s[i+1].x-s[i].x)==maxx) { cout<<s[i].num<<" "<<s[i+1].num<<endl; break; } } return 0; }