#1193029 (C++23) No.2012 Largest Triangle

• 問題: No.2012 Largest Triangle
• ユーザー: leeh18
• 提出日時: 2026-10-13 16:57:20
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 152 ms / 2,500 ms
• コード長: 6,155 bytes
• コンパイル時間: 2,822 ms
• コンパイル使用メモリ: 348,216 KB
• 実行使用メモリ: 9,904 KB
• 最終ジャッジ日時: 2026-10-13 16:57:29
• 合計ジャッジ時間: 8,850 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge1_0

ファイルパターン	結果
sample	AC * 1
other	AC * 41

ソースコード

#include <bits/stdc++.h>

// https://github.com/hitonanode/cplib-cpp/blob/master/rational/rational_number.hpp
template <typename T, bool reduce = false> struct rational {
    constexpr rational(T num = 0, T den = 1) : p(num), q(den) { normalize(); }

    constexpr bool is_finite() const { return q != 0; }
    constexpr bool is_infinite() const { return p != 0 && q == 0; }
    constexpr bool is_nan() const { return p == 0 && q == 0; }

    constexpr rational &operator+=(const rational &o) {
        if (is_nan() || o.is_nan())
            return *this = rational(0, 0);
        if (is_infinite() && o.is_infinite())
            return *this = rational(p + o.p, 0);
        return *this = rational(p * o.q + q * o.p, q * o.q);
    }
    constexpr rational &operator-=(const rational &o) {
        if (is_nan() || o.is_nan())
            return *this = rational(0, 0);
        if (is_infinite() && o.is_infinite())
            return *this = rational(p - o.p, 0);
        return *this = rational(p * o.q - q * o.p, q * o.q);
    }
    constexpr rational &operator*=(const rational &o) { return *this = rational(p * o.p, q * o.q); }
    constexpr rational &operator/=(const rational &o) {
        if (o.p < 0)
            return *this = rational(p * -o.q, -q * o.p);
        return *this = rational(p * o.q, q * o.p);
    }

    friend constexpr rational operator+(rational a, const rational &b) { return a += b; }
    friend constexpr rational operator-(rational a, const rational &b) { return a -= b; }
    friend constexpr rational operator*(rational a, const rational &b) { return a *= b; }
    friend constexpr rational operator/(rational a, const rational &b) { return a /= b; }

    constexpr rational operator-() const { return rational(-p, q); }
    constexpr rational abs() const { return rational(0 < p ? p : -p, q); }
    constexpr T floor() const {
        assert(is_finite());
        return floor_div(p, q);
    }
    constexpr T ceil() const {
        assert(is_finite());
        return ceil_div(p, q);
    }

    constexpr std::partial_ordering operator<=>(const rational &r) const {
        if (is_nan() || r.is_nan()) {
            return std::partial_ordering::unordered;
        }
        if (is_infinite() && r.is_infinite()) {
            return p <=> r.p;
        }
        if (is_infinite()) {
            return p < 0 ? std::partial_ordering::less : std::partial_ordering::greater;
        }
        if (r.is_infinite()) {
            return r.p < 0 ? std::partial_ordering::greater : std::partial_ordering::less;
        }
        using W = std::conditional_t<sizeof(T) <= sizeof(int), long long, __int128_t>;
        return (W(p) * r.q) <=> (W(r.p) * q);
    }
    constexpr bool operator==(const rational &r) const { return (*this <=> r) == 0; }

    constexpr explicit operator double() const { return (double)p / (double)q; }
    constexpr explicit operator long double() const { return (long double)p / (long double)q; }

    constexpr T numerator() const { return p; }
    constexpr T denominator() const { return q; }

private:
    constexpr void normalize() {
        if (q == 0) {
            p = (p > 0) - (p < 0);
            return;
        }
        if constexpr (reduce) {
            T g = __gcd(p, q);
            if (g) {
                p /= g;
                q /= g;
            }
        }
        if (q < 0) {
            p = -p;
            q = -q;
        }
    }

    T p, q; // 0 <= q
};

// https://github.com/kth-competitive-programming/kactl/blob/main/content/data-structures/LineContainer.h
template <typename T, bool maximize = true> struct line_container {
    struct line {
        T a, b;
        mutable rational<T> p;
        bool operator<(const line &o) const { return a < o.a; }
        bool operator<(auto x) const { return p < x; }
    };
    static constexpr auto inf = rational<T>(1, 0);
    bool isect(auto x, auto y) {
        if (y == lines.end()) {
            x->p = inf;
            return false;
        }
        if (x->a == y->a) {
            x->p = (y->b < x->b) ? inf : -inf;
        } else {
            x->p = rational<T>(y->b - x->b, x->a - y->a);
        }
        return x->p >= y->p;
    }
    void add(T a, T b) {
        if constexpr (!maximize) {
            a = -a;
            b = -b;
        }
        auto z = lines.emplace(a, b, 0);
        auto y = z++;
        auto x = y;
        while (isect(y, z)) {
            z = lines.erase(z);
        }
        if (x != lines.begin() && isect(--x, y)) {
            y = lines.erase(y);
            isect(x, y);
        }
        while ((y = x) != lines.begin() && (--x)->p >= y->p) {
            isect(x, lines.erase(y));
        }
    }
    std::pair<T, T> query_line(auto x) const {
        assert(!lines.empty());
        auto l = lines.lower_bound(x);
        if constexpr (maximize) {
            return {l->a, l->b};
        } else {
            return {-l->a, -l->b};
        }
    }
    T query(T x) const {
        auto [a, b] = query_line(x);
        return a * x + b;
    }

private:
    std::multiset<line, std::less<>> lines;
};

template <typename T> struct line_container_2d {
    void add(T a, T b) {
        min_a = std::min(min_a, a);
        max_a = std::max(max_a, a);
        min_lc.add(a, b);
        max_lc.add(a, b);
    }
    T max(T x, T y) const {
        if (y == 0) {
            return x < 0 ? x * min_a : x * max_a;
        }
        rational<T> r(x, y);
        auto [a, b] = (y < 0 ? min_lc.query_line(r) : max_lc.query_line(r));
        return a * x + b * y;
    }
    T min(T x, T y) const { return -max(-x, -y); }
    static constexpr auto inf = std::numeric_limits<T>::max();
    T min_a = inf, max_a = -inf;
    line_container<T, false> min_lc;
    line_container<T> max_lc;
};

int main() {
    std::cin.tie(0)->sync_with_stdio(0);
    int N;
    std::cin >> N;
    std::vector<std::pair<int, int>> P(N);
    line_container_2d<long long> lc;
    for (auto &[x, y] : P) {
        std::cin >> x >> y;
        lc.add(x, y);
    }
    auto ans = 0LL;
    for (auto [x, y] : P) {
        ans = std::max({ans, lc.max(y, -x), lc.max(-y, x)});
    }
    std::cout << ans << "\n";
}