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

• 問題: No.2012 Largest Triangle
• ユーザー: leeh18
• 提出日時: 2026-10-13 16:46:21
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 151 ms / 2,500 ms
• コード長: 6,987 bytes
• コンパイル時間: 2,899 ms
• コンパイル使用メモリ: 347,260 KB
• 実行使用メモリ: 9,912 KB
• 最終ジャッジ日時: 2026-10-13 16:46:31
• 合計ジャッジ時間: 9,162 ms
• ジャッジサーバーID （参考情報）: judge4_0 / judge2_0

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

ソースコード

#include <bits/stdc++.h>
using namespace std;

// clang-format off
using i8 = signed char; using u8 = unsigned char;
using i32 = int;        using u32 = unsigned;
using i64 = long long;  using u64 = unsigned long long;
using i128 = __int128;  using u128 = unsigned __int128;
template <typename T> T ceil_div(T a, T b) { return a / b + static_cast<T>((a ^ b) > 0 && a % b != 0); }
template <typename T> T floor_div(T a, T b) { return a / b - static_cast<T>((a ^ b) < 0 && a % b != 0); }
template <int I = 0> void read(auto &a) { for (auto &x : a) { cin >> x; if constexpr (I) { x -= I; } } }
template <int I = 0> void show(const auto &a, string_view sep = " ", string_view end = "\n") {
    for (auto it = a.begin(); it != a.end(); ++it) { if (it != a.begin()) { cout << sep; }
    auto x = *it; if constexpr (I) { x += I; } cout << x; } cout << end;
}
// clang-format on

// 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 partial_ordering::unordered;
        }
        if (is_infinite() && r.is_infinite()) {
            return p <=> r.p;
        }
        if (is_infinite()) {
            return p < 0 ? partial_ordering::less : partial_ordering::greater;
        }
        if (r.is_infinite()) {
            return r.p < 0 ? partial_ordering::greater : 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 (!maximize) {
            a *= -1, b *= -1;
        }
        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));
        }
    }
    T query(T x) {
        assert(!lines.empty());
        auto l = *lines.lower_bound(x);
        auto y = l.a * x + l.b;
        return maximize ? y : -y;
    }
    pair<T, T> get(auto x) {
        assert(!lines.empty());
        auto l = *lines.lower_bound(x);
        auto k = maximize ? 1 : -1;
        return {k * l.a, k * l.b};
    }

private:
    multiset<line, 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) {
        if (y == 0) {
            return x < 0 ? x * min_a : x * max_a;
        }
        rational<T> r(x, y);
        auto [a, b] = (y < 0 ? min_lc.get(r) : max_lc.get(r));
        return a * x + b * y;
    }
    T min(T x, T y) { return -max(-x, -y); }
    static constexpr auto inf = numeric_limits<T>::max();
    T min_a = inf, max_a = -inf;
    line_container<T, false> min_lc;
    line_container<T> max_lc;
};

void solve() {
    int N;
    cin >> N;
    vector<pair<int, int>> P(N);
    line_container_2d<i64> lc;
    for (auto &[x, y] : P) {
        cin >> x >> y;
        lc.add(x, y);
    }
    i64 ans = 0;
    for (auto [x, y] : P) {
        ans = max({ans, lc.max(y, -x), lc.max(-y, x)});
    }
    cout << ans << "\n";
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int t = 1;
#ifdef TC
    cin >> t;
#endif
    for (auto i = 0; i < t; ++i) {
        solve();
    }
}