51nod 1100 斜率最大

可以用三个点简单证明斜率最大的直线两个点！

#include <bits/stdc++.h>

#define MAXN 10010

using namespace std;

struct Node{

    int x, y, number;

}gg[MAXN];

bool cmp(Node a, Node b){

    return a.x<b.x;

}

int main(void){

    std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);

    int n;

    cin >> n;

    for(int i=0; i<n; i++){

        cin >> gg[i].x >> gg[i].y;

        gg[i].number=i+1;

    }

    sort(gg, gg+n, cmp);

    queue<int> node1, node2;

    double cnt=0, cc=0;

    for(int i=1; i<n; i++){

        cnt=(gg[i].y-gg[i-1].y)*1.0/(gg[i].x-gg[i-1].x);

        if(cnt>cc){

            cc=cnt;

            while(!node1.empty()){

                node1.pop();

            }

            while(!node2.empty()){

                node2.pop();

            }

            node1.push(gg[i-1].number);

            node2.push(gg[i].number);

        }else if(cnt==cc){

            node1.push(gg[i-1].number);

            node2.push(gg[i].number);

        }

    }

    while(!node1.empty()){

        cout << node1.front() << " " << node2.front() << endl;

        node1.pop();

        node2.pop();

    }

    return 0;

}

巴特西

51nod 1100 斜率最大

最新文章

热门文章