test/yosupo/furthest_pair.test.cpp

View this file on GitHub
Last update: 2025-01-11 18:51:05+09:00
Problem: https://judge.yosupo.jp/problem/furthest_pair

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/furthest_pair"

#include "../../geometry/furthest_pair.hpp"

#include <bits/stdc++.h>

#include "../../geometry/geometry.hpp"
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(15);

    int T;
    cin >> T;
    while (T--) {
        int N;
        cin >> N;
        vector<Vec> pts(N);
        for (auto& p : pts) cin >> p;
        auto [d, i, j] = furthest_pair(pts);
        cout << i << " " << j << "\n";
    }
}

#line 1 "test/yosupo/furthest_pair.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/furthest_pair"

#line 2 "geometry/furthest_pair.hpp"
#include <algorithm>
#include <utility>
#include <vector>

#line 3 "geometry/convex_hull.hpp"

#line 3 "geometry/geometry.hpp"
#include <cassert>
#include <cmath>
#include <complex>
#include <iostream>
#include <numbers>
#include <numeric>
#line 10 "geometry/geometry.hpp"

// note that if T is of an integer type, std::abs does not work
using T = double;
using Vec = std::complex<T>;

std::istream& operator>>(std::istream& is, Vec& p) {
    T x, y;
    is >> x >> y;
    p = {x, y};
    return is;
}

T dot(const Vec& a, const Vec& b) { return (std::conj(a) * b).real(); }

T cross(const Vec& a, const Vec& b) { return (std::conj(a) * b).imag(); }

constexpr T PI = std::numbers::pi_v<T>;
constexpr T eps = 1e-10;
inline bool eq(T a, T b) { return std::abs(a - b) <= eps; }
inline bool eq(Vec a, Vec b) { return std::abs(a - b) <= eps; }
inline bool lt(T a, T b) { return a < b - eps; }
inline bool leq(T a, T b) { return a <= b + eps; }

struct Line {
    Vec p1, p2;
    Line() = default;
    Line(const Vec& p1, const Vec& p2) : p1(p1), p2(p2) {}
    Vec dir() const { return p2 - p1; }
};

struct Segment : Line {
    using Line::Line;
};

struct Circle {
    Vec c;
    T r;
    Circle() = default;
    Circle(const Vec& c, T r) : c(c), r(r) {}
};

using Polygon = std::vector<Vec>;

Vec rot(const Vec& a, T ang) { return a * Vec(std::cos(ang), std::sin(ang)); }

Vec perp(const Vec& a) { return Vec(-a.imag(), a.real()); }

Vec projection(const Line& l, const Vec& p) {
    return l.p1 + dot(p - l.p1, l.dir()) * l.dir() / std::norm(l.dir());
}

Vec reflection(const Line& l, const Vec& p) {
    return T(2) * projection(l, p) - p;
}

// 0: collinear
// 1: counter-clockwise
// -1: clockwise
int ccw(const Vec& a, const Vec& b, const Vec& c) {
    if (eq(cross(b - a, c - a), 0)) return 0;
    if (lt(cross(b - a, c - a), 0)) return -1;
    return 1;
}

void sort_by_arg(std::vector<Vec>& pts) {
    std::ranges::sort(pts, [&](auto& p, auto& q) {
        if ((p.imag() < 0) != (q.imag() < 0)) return (p.imag() < 0);
        if (cross(p, q) == 0) {
            if (p == Vec(0, 0))
                return !(q.imag() < 0 || (q.imag() == 0 && q.real() > 0));
            if (q == Vec(0, 0))
                return (p.imag() < 0 || (p.imag() == 0 && p.real() > 0));
            return (p.real() > q.real());
        }
        return (cross(p, q) > 0);
    });
}
#line 5 "geometry/convex_hull.hpp"

std::vector<Vec> convex_hull(std::vector<Vec> pts, bool strict = true) {
    std::ranges::sort(pts, {}, [](const Vec& v) {
        return std::make_pair(v.imag(), v.real());
    });
    if (strict) {
        pts.erase(std::ranges::unique(pts).begin(), pts.end());
    }
    const int n = pts.size();
    if (n <= 1) return pts;
    int k = 0;  // the number of vertices in the convex hull
    std::vector<Vec> ch(2 * n);
    // right
    for (int i = 0; i < n; ++i) {
        if (strict) {
            while (k > 1 &&
                   leq(cross(ch[k - 1] - ch[k - 2], pts[i] - ch[k - 1]), 0))
                --k;
        } else {
            while (k > 1 &&
                   lt(cross(ch[k - 1] - ch[k - 2], pts[i] - ch[k - 1]), 0))
                --k;
        }
        ch[k++] = pts[i];
    }
    int t = k;
    // left
    for (int i = n - 2; i >= 0; --i) {
        if (strict) {
            while (k > t &&
                   leq(cross(ch[k - 1] - ch[k - 2], pts[i] - ch[k - 1]), 0))
                --k;
        } else {
            while (k > t &&
                   lt(cross(ch[k - 1] - ch[k - 2], pts[i] - ch[k - 1]), 0))
                --k;
        }
        ch[k++] = pts[i];
    }
    ch.resize(k - 1);
    return ch;
}
#line 8 "geometry/furthest_pair.hpp"

/**
 * @brief Furthest Pair
 */
std::tuple<T, int, int> furthest_pair(const std::vector<Vec>& pts) {
    assert(pts.size() >= 2);
    auto conv = convex_hull(pts);
    const int n = conv.size();
    if (n <= 1) {
        return {0, 0, 1};
    }
    std::tuple<T, int, int> furthest;
    if (n == 2) {
        furthest = {std::abs(conv[0] - conv[1]), 0, 1};
    } else {
        int si = 0, sj = 0;
        for (int k = 0; k < n; ++k) {
            if (lt(conv[k].real(), conv[si].real())) si = k;
            if (lt(conv[sj].real(), conv[k].real())) sj = k;
        }
        for (int i = si, j = sj; i != sj || j != si;) {
            furthest = std::max(furthest, {std::abs(conv[i] - conv[j]), i, j});
            if (lt(cross(conv[(i + 1) % n] - conv[i],
                         conv[(j + 1) % n] - conv[j]),
                   0)) {
                i = (i + 1) % n;
            } else {
                j = (j + 1) % n;
            }
        }
    }
    auto [d, i0, j0] = furthest;
    int i1 = -1, j1 = -1;
    for (int k = 0; k < (int)pts.size(); ++k) {
        if (i1 == -1 && pts[k] == conv[i0]) i1 = k;
        if (j1 == -1 && pts[k] == conv[j0]) j1 = k;
    }
    return {d, i1, j1};
}
#line 4 "test/yosupo/furthest_pair.test.cpp"

#include <bits/stdc++.h>

#line 8 "test/yosupo/furthest_pair.test.cpp"
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(15);

    int T;
    cin >> T;
    while (T--) {
        int N;
        cin >> N;
        vector<Vec> pts(N);
        for (auto& p : pts) cin >> p;
        auto [d, i, j] = furthest_pair(pts);
        cout << i << " " << j << "\n";
    }
}