題干：

平面上有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軸坐標）

Sample Input

5 1 2 6 8 4 4 5 4 2 3

Sample Output

4 2

解題報告：

? ? ? 貪心排序。

AC代碼：

#include<bits/stdc++.h>using namespace std; const double eps = 1e-8; const int MAX = 10000 + 5; struct Point {int x,y;int id; } p[MAX]; struct Node {int id1,id2;double k;Node(){}Node(int id1,int id2,double k):id1(id1),id2(id2),k(k){}} node[MAX]; bool cmp(const Point &a ,const Point &b) {return a.x<b.x; } bool cmp2(const Node a,const Node b) {return a.k>b.k; } int main() {int n;double kk;cin>>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,cmp);for(int i = 1; i<=n-1; i++) {kk = (p[i+1].y-p[i].y)*1.0/(p[i+1].x-p[i].x); // node[i] = Node(p[i].id,p[i+1].id,kk);Node tmp;node[i].id1 = p[i].id;node[i].id2 = p[i+1].id; node[i].k = kk; }sort(node+1,node+n,cmp2); // for(int i = 1; i<=n-1; i++) // cout<< node[i].k<<endl;double maxx = node[1].k;for(int i = 1; i<=n-1; i++) {if( abs(node[i].k - maxx) <= eps) {printf("%d %d\n",node[i].id1,node[i].id2);}else break;}return 0 ;}

總結：

? ?最后那個判斷要加abs的！！！！不然樣例就錯了，就全輸出。。?

?

總結

以上是生活随笔為你收集整理的【51Nod-1100】 斜率最大（贪心）☆双排序的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。