test/yukicoder/2012.test.cpp

• View this file on GitHub
• Last update: 2025-11-24 18:49:07+09:00
• Problem: https://yukicoder.me/problems/no/2012
• Link: View error logs on GitHub Actions

Depends on

• build/pch/stdc++.hpp
• library/linearalgebra/ConvexHullTrick.hpp
• library/linearalgebra/Linear.hpp
• library/r2/XY.hpp

Code

#define PROBLEM "https://yukicoder.me/problems/no/2012"
#include <bits/stdc++.h>

#include "library/linearalgebra/ConvexHullTrick.hpp"
#include "library/r2/XY.hpp"
using ll = long long;
using ld = long double;
void chmax(ld &a, ld b) {
    if (a < b)
        a = b;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    std::cin >> n;
    std::vector<XY<ld>> xy(n);
    for (int i = 0; i < n; i++)
        std::cin >> xy[i];
    std::ranges::sort(xy);

    MinConvexHullTrick<ld> CHT1;
    MaxConvexHullTrick<ld> CHT2;

    ld ans = 0;

    for (const auto &v : xy) {
        if (v.x == 0) {
            chmax(ans, abs(xy[0].x * v.y));
            chmax(ans, abs(xy.back().x * v.y));
            continue;
        }
        if (CHT1.size()) {
            chmax(ans, abs(CHT1.query(v.y / v.x) * v.x));
            chmax(ans, abs(CHT2.query(v.y / v.x) * v.x));
        }
        Line<ld> f(v.x, -v.y);
        CHT1.add(f);
        CHT2.add(f);
    }
    std::cout << ll(round(ans)) << '\n';
}

#line 1 "test/yukicoder/2012.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/2012"
#include <bits/stdc++.h>

#line 2 "library/linearalgebra/Linear.hpp"
template <typename T> struct Line {
    T a, b;
    Line() = default;
    Line(T a, T b) : a(a), b(b) {}
    Line(std::pair<T, T> l) : a(l.first), b(l.second) {}
    Line(T c) : a(0), b(c) {}

    T operator()(const T x) const { return a * x + b; }
    Line operator()(const Line &l) const { return Line(a * l.a, a * l.b + b); }

    bool operator==(const Line &l) const { return a == l.a and b == l.b; }
    bool operator!=(const Line &l) const { return !(*this == l); }
    bool operator<(const Line &l) const {
        return (a == l.a ? a < l.a : b < l.b);
    }

    Line &operator+=(const Line &l) {
        a += l.a;
        b += l.b;
        return *this;
    }
    Line operator+(const Line &l) const { return Line(*this) += l; }
    Line &operator-=(const Line &l) {
        a -= l.a;
        b -= l.b;
        return *this;
    }
    Line operator-(const Line &l) const { return Line(*this) -= l; }
    Line operator-() const { return Line(-a, -b); }

    Line &operator+=(const T &c) {
        b += c;
        return *this;
    }
    Line operator+(const T &c) const { return Line(*this) += c; }
    Line &operator-=(const T &c) {
        b -= c;
        return *this;
    }
    Line operator-(const T &c) const { return Line(*this) -= c; }
    Line &operator*=(const T &c) {
        a *= c;
        b *= c;
        return *this;
    }
    Line operator*(const T &c) const { return Line(*this) *= c; }
    Line &operator/=(const T &c) {
        a /= c;
        b /= c;
        return *this;
    }
    Line operator/(const T &c) const { return Line(*this) /= c; }

    Line inv() const {
        assert(a != 0);
        return Line(T(1) / a, -b / a);
    }

    friend std::istream &operator>>(std::istream &is, Line &l) {
        is >> l.a >> l.b;
        return is;
    }
    friend std::ostream &operator<<(std::ostream &os, const Line &l) {
        if (l.a == 0 and l.b == 0)
            os << 0;
        else if (l.a == 0)
            os << l.b;
        else if (l.b == 0)
            os << l.a << "x";
        else if (l.b > 0)
            os << l.a << "x+" << l.b;
        else
            os << l.a << "x-" << -l.b;
        return os;
    }
};
#line 3 "library/linearalgebra/ConvexHullTrick.hpp"
namespace convex_hull_trick {
enum Objective {
    MINIMIZE = +1,
    MAXIMIZE = -1,
};

// 最大化の場合は反転して、内部では最小化問題のみを扱う
// 傾きが狭義単調減少になるように保存

template <typename T, Objective OBJ>
class ConvexHullTrick : std::deque<Line<T>> {
    using L = Line<T>;
    using std::deque<L>::push_back;
    using std::deque<L>::push_front;
    using std::deque<L>::pop_back;
    using std::deque<L>::pop_front;

    const L& at(int i) const { 
        return i >= 0 ? std::deque<L>::at(i) : std::deque<L>::at(size() + i);
    }

    static bool check(const L &l1, const L &l2, const L &l3) {
        // l2 が要らないなら true を返す
        // 傾きが狭義単調減少は保証されてる
        // 交点の x 座標は (l2.b-l1.b)/(l1.a-l2.a) と (l3.b-l2.b)/(l2.a-l3.a)
        // これが >= だと要らない
        return (l2.b - l1.b) * (l2.a - l3.a) >= (l3.b - l2.b) * (l1.a - l2.a);
    }

    static T apply_objective(const T &value) {
        if constexpr (OBJ == Objective::MINIMIZE)
            return value;
        else
            return -value;
    }

    void internal_push_back(const L &l) {
        assert(!size() or at(-1).a >= l.a);

        if(size() and at(-1).a == l.a) 
            if(at(-1).b <= l.b)
                return;
            else
                pop_back();
        
        while (size() >= 2 and check(at(-2), at(-1), l)) 
            pop_back();
        
        push_back(l);
    }

    void internal_push_front(const L &l) {
        assert(!size() or l.a >= at(0).a);

        if(size() and at(0).a == l.a)
            if(at(0).b <= l.b)
                return;
            else
                pop_front();

        while (size() >= 2 and check(l, at(0), at(1)))
            pop_front();
        
        push_front(l);
    }
  public:
    using value_type = L;
    using std::deque<L>::size;

    ConvexHullTrick() = default;
    ConvexHullTrick(std::vector<L> lines) {
        if (OBJ == -1)
            for (auto &l : lines)
                l = -l;
        std::ranges::sort(lines);
        for (const auto &l : lines)
            internal_push_back(l);
    }

    void add(L l) {
        if (OBJ == -1)
            l = -l;
        if (!size() or at(-1).a >= l.a)
            internal_push_back(l);
        else if (l.a >= at(0).a)
            internal_push_front(l);
        else
            assert(false);
    }

    void add(T a, T b) { add(L(a, b)); }

    // return min_f{f(x)}
    T query(T x) const {
        assert(size());
        int l = -1, r = size() - 1;
        while (r - l > 1) {
            int m = (l + r) >> 1;
            (at(m)(x) >= at(m + 1)(x) ? l : r) = m;
        }
        return apply_objective(at(r)(x));
    }

    // return min_f{f(x)}
    // 任意の X<x に対して f = argmin_f{f(X)} とならない f を全て削除する
    T query_monotone_inc(T x) {
        assert(size());
        while (size() >= 2 and at(0)(x) >= at(1)(x))
            pop_front();
        return apply_objective(at(0)(x));
    }

    // return min_f{f(x)}
    // 任意の X>x に対して f = argmin_f{f(X)} とならない f を全て削除する
    T query_monotone_dec(T x) {
        assert(size());
        while (size() >= 2 and at(-2)(x) <= at(-1)(x))
            pop_back();
        return apply_objective(at(-1)(x));
    }

    std::vector<T> query(const std::vector<T> &xs) {
        int n = xs.size();
        std::vector<int> idx(n);
        std::iota(idx.begin(), idx.end(), 0);
        std::ranges::sort(idx, std::ranges::less{}, [&](int i) { return xs[i]; });
        std::vector<T> ans(n);
        for (int id : idx)
            ans[id] = query_monotone_inc(xs[id]); 
        return ans;
    }

    friend std::ostream &operator<<(std::ostream &os,
                                    const ConvexHullTrick &cht) {
        os << "[";
        for (int i = 0; i < cht.size(); i++)
            os << (OBJ == -1 ? -cht.at(i) : cht.at(i))
               << "],"[i + 1 < cht.size()];
        if (!cht.size())
            os << "]";
        return os;
    }
};
} // namespace convex_hull_trick
template <typename T>
using MinConvexHullTrick =
    convex_hull_trick::ConvexHullTrick<T,
                                       convex_hull_trick::Objective::MINIMIZE>;
template <typename T>
using MaxConvexHullTrick =
    convex_hull_trick::ConvexHullTrick<T,
                                       convex_hull_trick::Objective::MAXIMIZE>;
#line 2 "library/r2/XY.hpp"
template <typename T> struct XY {
    T x, y;
    XY() = default;
    XY(T x, T y) : x(x), y(y) {}
    XY(const std::pair<T, T> &xy) : x(xy.first), y(xy.second) {}

    XY operator+() const { return *this; }
    XY operator-() const { return XY(-x, -y); }

    XY &operator++() {
        x++;
        y++;
        return *this;
    }
    XY &operator--() {
        x--;
        y--;
        return *this;
    }
    XY &operator++(int) {
        XY a = *this;
        ++*this;
        return a;
    }
    XY &operator--(int) {
        XY a = *this;
        --*this;
        return a;
    }

    XY &operator+=(const XY &v) {
        x += v.x;
        y += v.y;
        return *this;
    }
    XY &operator-=(const XY &v) {
        x -= v.x;
        y -= v.y;
        return *this;
    }
    XY &operator*=(const T &a) {
        x *= a;
        y *= a;
        return *this;
    }
    XY &operator/=(const T &a) {
        x /= a;
        y /= a;
        return *this;
    }

    friend XY operator+(const XY &u, const XY &v) { return XY(u) += v; }
    friend XY operator-(const XY &u, const XY &v) { return XY(u) -= v; }
    friend XY operator*(const XY &u, const T &a) { return XY(u) *= a; }
    friend XY operator*(const T &a, const XY &u) { return XY(u) *= a; }
    friend XY operator/(const XY &u, const T &a) { return XY(u) /= a; }

    bool operator<(const XY &v) const { return x != v.x ? x < v.x : y < v.y; }
    bool operator>(const XY &v) const { return x != v.x ? x > v.x : y > v.y; }
    bool operator==(const XY &v) const { return x == v.x and y == v.y; }
    bool operator<=(const XY &v) const { return !(*this > v); }
    bool operator>=(const XY &v) const { return !(*this < v); }
    bool operator!=(const XY &v) const { return !(*this == v); }

    double arg() const { return atan2(y, x); }

    // [0,2pi) で θ(u)<θ(v) の時 true
    // (0,0) は 2pi に相当
    // static bool angle_cmp(const XY&u,const XY&v){
    //  using U=conditional_t< is_same_v<T,int>,long long,T>;
    //  if(u==XY(0,0))return false;
    //  if(v==XY(0,0))return true;
    //  if(u.y==0){
    //    if(u.x>0)return true;
    //    if(v.y==0)return v.x<0;
    //    return v.y<0;
    //  }
    //  if(u.y>0){
    //    if(v.y==0)return v.x<0;
    //    if(v.y<0)return true;
    //    return U(v.x)*u.y <= U(u.x)*v.y;
    //  }
    //  if(v.y>=0)return false;
    //  return U(v.x)*u.y <= U(u.x)*v.y;
    //}

    friend T dot(const XY &u, const XY &v) { return u.x * v.x + u.y * v.y; }
    T norm() { return dot(*this, *this); }
    T abs() { return sqrt(norm()); }

    friend std::istream &operator>>(std::istream &is, XY &v) {
        is >> v.x >> v.y;
        return is;
    }
    friend std::ostream &operator<<(std::ostream &os, const XY &v) {
        os << v.x << " " << v.y;
        return os;
    }

    static XY direction(const char &c) {
        if (c == 'R')
            return {1, 0};
        if (c == 'L')
            return {-1, 0};
        if (c == 'U')
            return {0, -1};
        if (c == 'D')
            return {0, 1};
        return {0, 0};
    }
};
#line 6 "test/yukicoder/2012.test.cpp"
using ll = long long;
using ld = long double;
void chmax(ld &a, ld b) {
    if (a < b)
        a = b;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    std::cin >> n;
    std::vector<XY<ld>> xy(n);
    for (int i = 0; i < n; i++)
        std::cin >> xy[i];
    std::ranges::sort(xy);

    MinConvexHullTrick<ld> CHT1;
    MaxConvexHullTrick<ld> CHT2;

    ld ans = 0;

    for (const auto &v : xy) {
        if (v.x == 0) {
            chmax(ans, abs(xy[0].x * v.y));
            chmax(ans, abs(xy.back().x * v.y));
            continue;
        }
        if (CHT1.size()) {
            chmax(ans, abs(CHT1.query(v.y / v.x) * v.x));
            chmax(ans, abs(CHT2.query(v.y / v.x) * v.x));
        }
        Line<ld> f(v.x, -v.y);
        CHT1.add(f);
        CHT2.add(f);
    }
    std::cout << ll(round(ans)) << '\n';
}

Back to top page