結果

問題 No.2012 Largest Triangle
ユーザー Carpenters-CatCarpenters-Cat
提出日時 2022-07-15 22:46:25
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 232 ms / 2,500 ms
コード長 15,722 bytes
コンパイル時間 2,218 ms
コンパイル使用メモリ 149,620 KB
実行使用メモリ 7,032 KB
最終ジャッジ日時 2023-09-10 05:48:00
合計ジャッジ時間 8,675 ms
ジャッジサーバーID
(参考情報)
judge14 / judge11
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,380 KB
testcase_01 AC 2 ms
4,376 KB
testcase_02 AC 2 ms
4,380 KB
testcase_03 AC 2 ms
4,376 KB
testcase_04 AC 2 ms
4,376 KB
testcase_05 AC 2 ms
4,380 KB
testcase_06 AC 2 ms
4,380 KB
testcase_07 AC 1 ms
4,380 KB
testcase_08 AC 2 ms
4,380 KB
testcase_09 AC 2 ms
4,376 KB
testcase_10 AC 1 ms
4,380 KB
testcase_11 AC 1 ms
4,376 KB
testcase_12 AC 1 ms
4,380 KB
testcase_13 AC 1 ms
4,380 KB
testcase_14 AC 2 ms
4,376 KB
testcase_15 AC 2 ms
4,380 KB
testcase_16 AC 201 ms
6,224 KB
testcase_17 AC 201 ms
6,204 KB
testcase_18 AC 202 ms
6,228 KB
testcase_19 AC 203 ms
6,136 KB
testcase_20 AC 200 ms
6,208 KB
testcase_21 AC 200 ms
6,292 KB
testcase_22 AC 200 ms
6,160 KB
testcase_23 AC 201 ms
6,164 KB
testcase_24 AC 199 ms
6,168 KB
testcase_25 AC 199 ms
6,264 KB
testcase_26 AC 232 ms
6,684 KB
testcase_27 AC 229 ms
6,760 KB
testcase_28 AC 232 ms
6,764 KB
testcase_29 AC 232 ms
7,032 KB
testcase_30 AC 231 ms
6,784 KB
testcase_31 AC 214 ms
6,164 KB
testcase_32 AC 216 ms
6,220 KB
testcase_33 AC 213 ms
6,240 KB
testcase_34 AC 214 ms
6,148 KB
testcase_35 AC 214 ms
6,504 KB
testcase_36 AC 3 ms
4,380 KB
testcase_37 AC 3 ms
4,376 KB
testcase_38 AC 3 ms
4,380 KB
testcase_39 AC 3 ms
4,376 KB
testcase_40 AC 3 ms
4,376 KB
testcase_41 AC 69 ms
6,016 KB
権限があれば一括ダウンロードができます

ソースコード

diff #

#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <utility>
#include <vector>

// def_class
using namespace std;
using ll = long long;
using Vi = vector<int>;
using VVi = vector<Vi>;
using Vl = vector<ll>;
using VVl = vector<Vl>;
using Pii = pair<int, int>;
using Vp = vector<Pii>;
using VVp = vector<Vp>;
using Pl = pair<ll, int>;
using Vpl = vector<Pl>;
using VVpl = vector<Vpl>;
using tup = tuple<ll, ll, int>;
using Vt = vector<tuple<int, int, int>>;
using Pll = pair<ll, ll>;
using Vc = vector<char>;
using VVc = vector<Vc>;
template <class U>
using PQmax = priority_queue<U>;
template <class U>
using PQmin = priority_queue<U, vector<U>, greater<U>>;

// func_def
//再帰で計算するトポロジカルソート
void tprsort(int u, const VVi& gr, Vi& tpr, Vi& par);
void tprsort(int u, const VVpl& gr, Vi& tpr, Vi& par);
//キューで計算するトポロジカルソート
void tprsort(const VVi& gr, Vi& tpr);
ll mpow(ll x, ll n, ll m = 1e9 + 7);
ll comb(int n, int r, const Vl& kai, const Vl& fkai, ll m = 1e9 + 7);
ll gcd(ll a, ll b);
int LCA(const VVi& par, const Vi& depth, int a, int b);
Vi sccResolve(const VVi& gr);
void dijkstra(const VVi& gr, const VVl& cost, Vl& dist, int s);
void dijkstra_prev(const VVi& gr, const VVl& cost, Vl& dist, Vi& prev, int s);

// ax + by = c
struct DLine {
    ll a;
    ll b;
    ll c;
    bool operator<(const DLine l) const;
};
DLine make_dline(ll x1, ll y1, ll x2, ll y2);
double calc_tilt(DLine l1);
bool is_upper(DLine l, ll x, ll y);
bool is_inside(DLine l, ll x, ll y);

class unionfind
{
private:
    Vi par;
    Vi siz;

public:
    unionfind(int N);
    unionfind();
    int root(int v);
    void merge(int a, int b);
    bool same(int a, int b);
    int size(int a);
};
class w_unionfind
{
private:
    Vi par;
    Vi siz;
    Vi val;

public:
    w_unionfind(int N);
    w_unionfind();
    int root(int v);
    void merge(int a, int b, int z);
    bool same(int a, int b);
    int value(int a);
};
class BIT
{
private:
    Vl bit;
    int siz;

public:
    BIT(int N);
    BIT();
    ll& get(int id);
    void add(int id, ll a, ll m);
    ll sum(int id, ll m);
};
class RMQ
{
private:
    Vl val;
    int siz;
    ll e;
    ll prod_sub(int l, int r, int a, int b, int id);

public:
    RMQ(int N, ll e = (ll)1e18);
    RMQ(Vl A, ll e = (ll)1e18);
    RMQ(ll e = (ll)1e18);
    ll& get(int id);
    void set(int id, ll a);
    void add(int id, ll a);
    ll prod(int l, int r);
};
class Fraction
{
public:
    ll mot;
    ll son;

    // a/b を生成
    Fraction(ll a = 0, ll b = 1)
    {
        ll g = gcd(abs(a), abs(b));
        if (b < 0) {
            a *= -1;
            b *= -1;
        }
        mot = b / g;
        son = a / g;
    }
    Fraction(const Fraction& F) : mot(F.mot), son(F.son) {}
    Fraction operator+(const Fraction A) const;
    Fraction operator-(const Fraction A) const;
    Fraction operator*(const Fraction A) const;
    // Fraction operator/(const int& a);
    Fraction operator/(const Fraction A) const;
    Fraction operator=(const Fraction& A);
    bool operator<(const Fraction A) const;
    bool operator>(const Fraction A) const;
};

int main()
{
    int N;
    cin >> N;
    vector<Pll> A(N);
    for (auto& [a, b] : A) {
        cin >> a >> b;
    }
    sort(A.begin(), A.end());
    vector<Pll> U, D;
    vector<Fraction> uf, df;
    for (auto [a, b] : A) {
        if (U.size() < 2) {
            U.emplace_back(a, b);
        } else {
            while (U.size() >= 2) {
                auto [a1, b1] = U.back();
                auto [a2, b2] = U[U.size() - 2];
                ll da1 = a - a1;
                ll db1 = b - b1;
                ll da2 = a1 - a2;
                ll db2 = b1 - b2;
                if (da1 * db2 <= db1 * da2) {
                    U.pop_back();
                } else {
                    break;
                }
            }
            U.emplace_back(a, b);
        }
    }
    for (auto [a, b] : A) {
        if (D.size() < 2) {
            D.emplace_back(a, b);
        } else {
            while (D.size() >= 2) {
                auto [a1, b1] = D.back();
                auto [a2, b2] = D[D.size() - 2];
                ll da1 = a - a1;
                ll db1 = b - b1;
                ll da2 = a1 - a2;
                ll db2 = b1 - b2;
                if (da1 * db2 >= db1 * da2) {
                    D.pop_back();
                } else {
                    break;
                }
            }
            D.emplace_back(a, b);
        }
    }
    for (int i = 0; i < D.size() - 1; i++) {
        auto [p1, p2] = D[i];
        auto [q1, q2] = D[i + 1];
        df.push_back(Fraction{q2 - p2, q1 - p1});
    }
    for (int i = 0; i < U.size() - 1; i++) {
        auto [p1, p2] = U[i];
        auto [q1, q2] = U[i + 1];
        uf.push_back(Fraction{q2 - p2, q1 - p1});
    }
    for (int i = 0; i < uf.size() - 1; i ++) {
        assert(!(uf[i] < uf[i + 1]));
    }
    for (int i = 0; i < df.size() - 1; i ++) {
        assert(!(df[i] > df[i + 1]));
    }
    ll ans = 0;
    for (auto [a, b] : A) {
        Fraction F{b, a};
        int ma = D.size();
        int mi = 0;
        while (ma - mi > 1) {
            int mu = (ma + mi) / 2;
            if (df[mu - 1] < F) {
                mi = mu;
            } else {
                ma = mu;
            }
        }
        auto [x, y] = D[mi];
        ans = max(ans, abs(a * y - b * x));
        ma = U.size();
        mi = 0;
        while (ma - mi > 1) {
            int mu = (ma + mi) / 2;
            if (uf[mu - 1] > F) {
                mi = mu;
            } else {
                ma = mu;
            }
        }
        auto [x1, y1] = U[mi];
        ans = max(ans, abs(a * y1 - b * x1));
    }
    cout << ans << endl;
}
// Library

// pair<ll, int> 用
void tprsort(int u, const VVpl& gr, Vi& tpr, Vi& par)
{
    // idx[u] = tpr.size();
    /*for (int v : gr[u]) {
        if (par[v] == u || par[v] == -1) {
            par[v] = u;
            tprsort(v, gr, tpr, par);
        }
    }
    tpr.push_back(u);*/
    stack<int> st;
    st.push(u);
    bool vis[2000020];
    for (int i = 0; i <= gr.size(); i++) {
        vis[i] = false;
    }
    while (!st.empty()) {
        int v = st.top();
        if (!vis[v]) {
            vis[v] = true;
            for (auto [x, p] : gr[v]) {
                if (par[p] == -1) {
                    par[p] = v;
                    st.push(p);
                }
            }
        } else {
            tpr.push_back(v);
            st.pop();
        }
    }
}

//再帰型
void tprsort(int u, const VVi& gr, Vi& tpr, Vi& par)
{
    // idx[u] = tpr.size();
    /*for (int v : gr[u]) {
        if (par[v] == u || par[v] == -1) {
            par[v] = u;
            tprsort(v, gr, tpr, par);
        }
    }
    tpr.push_back(u);*/
    stack<int> st;
    st.push(u);
    bool vis[2000020];
    for (int i = 0; i <= gr.size(); i++) {
        vis[i] = false;
    }
    while (!st.empty()) {
        int v = st.top();
        if (!vis[v]) {
            vis[v] = true;
            for (int p : gr[v]) {
                if (par[p] == -1) {
                    par[p] = v;
                    st.push(p);
                }
            }
        } else {
            tpr.push_back(v);
            st.pop();
        }
    }
}

Vi sccResolve(const VVi& gr)
{
    int N = gr.size();
    Vi tpr;
    Vi par(N, -1);
    for (int i = 0; i < N; i++) {
        if (par[i] == -1) {
            tprsort(i, gr, tpr, par);
        }
    }
    Vi ret(N, -1);
    int now = 0;
    for (int i = N - 1; i >= 0; i--) {
        int u = tpr[i];
        if (ret[u] != -1) {
            continue;
        }
        ret[u] = now;
        stack<int> st;
        st.push(u);
        while (!st.empty()) {
            int v = st.top();
            st.pop();
            for (int p : gr[v]) {
                if (ret[p] == -1) {
                    st.push(p);
                    ret[p] = now;
                }
            }
        }
        now++;
    }
    return ret;
}

ll gcd(ll a, ll b)
{
    while (b) {
        a %= b;
        swap(a, b);
    }
    return a;
}
ll mpow(ll x, ll n, ll m)
{
    ll ret = 1;
    while (n) {
        if (n % 2) {
            ret *= x;
            ret %= m;
        }
        x = (x * x) % m;
        n /= 2;
    }
    return ret;
}
ll comb(int n, int r, const Vl& kai, const Vl& fkai, ll m)
{
    if (n < 0 || r < 0 || n < r) {
        return 0;
    }
    ll ret = kai[n];
    ret *= fkai[r];
    ret %= m;
    ret *= fkai[n - r];
    ret %= m;
    return ret;
}

int LCA(const VVi& par, const Vi& depth, int a, int b)
{
    if (depth[a] < depth[b]) {
        swap(a, b);
    }
    int dis = depth[a] - depth[b];
    for (int i = 19; i >= 0; i--) {
        if ((dis >> i) & 1) {
            a = par[i][a];
        }
    }
    if (a == b) {
        return a;
    }
    for (int i = 19; i >= 0; i--) {
        if (par[i][a] != par[i][b]) {
            a = par[i][a];
            b = par[i][b];
        }
    }
    return par[0][a];
}

void dijkstra(const VVi& gr, const VVl& cost, Vl& dist, int s)
{
    ll INF = (ll)1e18;
    dist.assign(gr.size(), INF);
    dist[s] = 0;
    PQmin<Pl> pque;
    pque.push(make_pair(0, s));
    while (!pque.empty()) {
        auto [L, u] = pque.top();
        pque.pop();
        while (L != dist[u] && !pque.empty()) {
            tie(L, u) = pque.top();
            pque.pop();
        }
        for (int i = 0; i < gr[u].size(); i++) {
            int v = gr[u][i];
            ll c = cost[u][i];
            if (dist[v] > c + L) {
                dist[v] = c + L;
                pque.push(make_pair(dist[v], v));
            }
        }
    }
    return;
}

void dijkstra_prev(const VVi& gr, const VVl& cost, Vl& dist, Vi& prev, int s)
{
    ll INF = (ll)1e18;
    dist.assign(gr.size(), INF);
    dist[s] = 0;
    PQmin<Pl> pque;
    pque.push(make_pair(0, s));
    while (!pque.empty()) {
        auto [L, u] = pque.top();
        pque.pop();
        while (L != dist[u] && !pque.empty()) {
            tie(L, u) = pque.top();
            pque.pop();
        }
        for (int i = 0; i < gr[u].size(); i++) {
            int v = gr[u][i];
            ll c = cost[u][i];
            if (dist[v] > c + L) {
                dist[v] = c + L;
                prev[v] = u;
                pque.push(make_pair(dist[v], v));
            }
        }
    }
    return;
}

DLine make_dline(ll x1, ll y1, ll x2, ll y2)
{
    ll dx = x1 - x2;
    ll dy = y2 - y1;
    if (dy < 0) {
        dx *= -1;
        dy *= -1;
    }
    if (dy == 0) {
        dx = abs(dx);
    }
    ll g = gcd(dy, abs(dx));
    dx /= g;
    dy /= g;
    ll c = dx * y1 + dy * x1;
    return DLine{dy, dx, c};
}
double calc_tilt(DLine l)
{
    return atan2(l.a, l.b);
}
bool is_upper(DLine l, ll x, ll y)
{
    return x * l.a + y * l.b > l.c;
}
bool is_inside(DLine l, ll x, ll y)
{
    return x * l.a + y * l.b == l.c;
}

unionfind::unionfind(int N)
{
    par.resize(N);
    siz.assign(N, 1);
    for (int i = 0; i < N; i++) {
        par[i] = i;
    }
}
unionfind::unionfind()
{
    par.resize(100010);
    siz.assign(100010, 1);
    for (int i = 0; i <= 100010; i++) {
        par[i] = i;
    }
}
int unionfind::root(int v)
{
    if (v == par[v]) {
        return v;
    }
    return par[v] = root(par[v]);
}
void unionfind::merge(int a, int b)
{
    a = root(a);
    b = root(b);
    if (a == b) {
        return;
    }
    if (siz[a] < siz[b]) {
        int t = a;
        a = b;
        b = t;
    }
    par[b] = a;
    siz[a] += siz[b];
}
bool unionfind::same(int a, int b)
{
    a = root(a);
    b = root(b);
    return a == b;
}
int unionfind::size(int a)
{
    return siz[this->root(a)];
}

w_unionfind::w_unionfind(int N)
{
    par.resize(N);
    siz.assign(N, 1);
    val.assign(N, 0);
    for (int i = 0; i < N; i++) {
        par[i] = i;
    }
}
w_unionfind::w_unionfind()
{
    par.resize(100010);
    siz.assign(100010, 1);
    val.assign(100010, 0);
    for (int i = 0; i <= 100010; i++) {
        par[i] = i;
    }
}
int w_unionfind::root(int v)
{
    if (v == par[v]) {
        return v;
    }
    int p = root(par[v]);
    val[v] += val[par[v]];
    par[v] = p;
    return p;
}
void w_unionfind::merge(int a, int b, int z)
{
    z -= this->value(b);
    z += this->value(a);
    a = root(a);
    b = root(b);
    if (a == b) {
        return;
    }
    if (siz[a] < siz[b]) {
        int t = a;
        a = b;
        b = t;
        z *= -1;
    }
    par[b] = a;
    siz[a] += siz[b];
    val[b] += z;
}
bool w_unionfind::same(int a, int b)
{
    a = root(a);
    b = root(b);
    return a == b;
}
int w_unionfind::value(int a)
{
    root(a);
    return val[a];
}


BIT::BIT(int N)
{
    siz = N;
    bit.assign(N + 1, 0);
}

BIT::BIT()
{
    siz = 0;
}

ll& BIT::get(int id)
{
    return bit[id];
}

void BIT::add(int id, ll a, ll m)
{
    while (id <= siz) {
        bit[id] += a;
        bit[id] %= m;
        id += (id & (-id));
    }
}

ll BIT::sum(int id, ll m)
{
    ll ret = 0;
    while (id) {
        ret += bit[id];
        ret %= m;
        id -= (id & (-id));
    }
    return ret;
}

RMQ::RMQ(int N, ll e)
{
    siz = 1;
    this->e = e;
    while (siz < N) {
        siz *= 2;
    }
    val.assign(siz * 2, e);
}
RMQ::RMQ(Vl A, ll e)
{
    siz = 1;
    this->e = e;
    while (siz < A.size()) {
        siz *= 2;
    }
    val.assign(siz * 2, e);
    for (int i = 0; i < A.size(); i++) {
        val[i + siz - 1] = A[i];
    }
    for (int i = siz - 2; i >= 0; i--) {
        int l = i * 2 + 1;
        int r = i * 2 + 2;
        val[i] = min(val[l], val[r]);
    }
}

RMQ::RMQ(ll e)
{
    siz = (1 << 20);
    this->e = e;
    val.assign(siz * 2, e);
}

ll& RMQ::get(int id)
{
    return val[id + siz - 1];
}

void RMQ::set(int id, ll a)
{
    id += siz - 1;
    val[id] = a;
    while (id > 0) {
        id = (id - 1) / 2;
        int l = id * 2 + 1;
        int r = id * 2 + 2;
        ll v = min(val[l], val[r]);
        /*if (val[id] == v) {
            break;
        }*/
        val[id] = v;
    }
}

void RMQ::add(int id, ll a)
{
    ll n = a + val[id + siz - 1];
    this->set(id, n);
}

ll RMQ::prod_sub(int l, int r, int a, int b, int id)
{
    if (b <= l || r <= a) {
        return this->e;
    }
    if (l <= a && b <= r) {
        return val[id];
    }
    return min(this->prod_sub(l, r, a, (a + b) / 2, id * 2 + 1),
        this->prod_sub(l, r, (a + b) / 2, b, id * 2 + 2));
}

ll RMQ::prod(int l, int r)
{
    return prod_sub(l, r, 0, siz, 0);
}

Fraction Fraction::operator+(const Fraction A) const
{
    return Fraction{this->son * A.mot + A.son * this->mot, this->mot * A.mot};
}
Fraction Fraction::operator-(const Fraction A) const
{
    return Fraction{this->son * A.mot - A.son * this->mot, this->mot * A.mot};
}
Fraction Fraction::operator*(const Fraction A) const
{
    return Fraction{this->son * A.son, this->mot * A.mot};
}
// Fraction Fraction::operator/(const int& a)
// {
//     return *this / (ll)a;
// }
Fraction Fraction::operator/(const Fraction A) const
{
    return Fraction{this->son * A.mot, this->mot * A.son};
}
Fraction Fraction::operator=(const Fraction& A)
{
    this->mot = A.mot;
    this->son = A.son;
    return *this;
}
bool Fraction::operator<(const Fraction A) const
{
    return this->son * A.mot < this->mot * A.son;
}
bool Fraction::operator>(const Fraction A) const
{
    return A < *this;
}
bool DLine::operator<(const DLine l) const
{
    if (a == l.a && b == l.b) {
        return c < l.c;
    }
    return Fraction{a, -b} < Fraction{l.a, -l.b};
}
0