斜率最大

51Nod-1100-斜率最大

分析

设x​A​​<x​B​​<x​C​​。

如果ABC三点共线，那么k​AB​​=k​BC​​=k​AC​​。

否则任意固定两点，上下移动另一点，得到的6种情况均满足max_k=max(k​AB​​,k​BC​​)。

实现

#include <iostream>
#include <algorithm>
#include <cmath>
#define inf 0x3f3f3f3f
using namespace std;

const int N = 10010;
const double eps = 1e-6;
struct node {
    int x, y;
    int idx;
    bool operator < (const node& o) const {
        return x < o.x;
    }
};
int n;
node a[N];
double k[N];

bool equal (const double& a, const double& b) {
    return fabs(a - b) < eps;
}

int main () {
    scanf("%d", &n);
    for (int i = 1, x, y; i <= n; ++ i) {
        scanf("%d%d", &x, &y);
        a[i] = { x, y, i };
    }

    sort(a + 1, a + n + 1);
    double max_k = -inf;
    for (int i = 2; i <= n; ++ i) {
        k[i] = double(a[i].y - a[i - 1].y) / (a[i].x - a[i - 1].x);
        max_k = max(max_k, k[i]);
    }

    for (int i = 2; i <= n; ++ i)
        if (equal(k[i], max_k))
            printf("%d %d", a[i - 1].idx, a[i].idx);
    return 0;
}