#778787 (C++17) No.2012 Largest Triangle

• 問題: No.2012 Largest Triangle
• ユーザー: satashun
• 提出日時: 2022-07-15 22:49:21
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: TLE (最新)
  AC
  (最初)
• 実行時間: -
• コード長: 14,094 bytes
• コンパイル時間: 2,882 ms
• コンパイル使用メモリ: 232,556 KB
• 実行使用メモリ: 28,544 KB
• 最終ジャッジ日時: 2024-06-27 21:21:50
• 合計ジャッジ時間: 15,879 ms
• ジャッジサーバーID （参考情報）: judge2 / judge4

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 10,624 KB
testcase_01	AC	2 ms; 5,376 KB
testcase_02	AC	2 ms; 5,376 KB
testcase_03	AC	2 ms; 5,376 KB
testcase_04	AC	2 ms; 5,376 KB
testcase_05	AC	2 ms; 5,376 KB
testcase_06	AC	2 ms; 5,376 KB
testcase_07	AC	2 ms; 5,376 KB
testcase_08	AC	2 ms; 5,376 KB
testcase_09	AC	2 ms; 5,376 KB
testcase_10	AC	2 ms; 5,376 KB
testcase_11	AC	2 ms; 5,376 KB
testcase_12	AC	2 ms; 5,376 KB
testcase_13	AC	2 ms; 5,376 KB
testcase_14	AC	2 ms; 5,376 KB
testcase_15	AC	2 ms; 5,376 KB
testcase_16	AC	159 ms; 28,348 KB
testcase_17	AC	159 ms; 28,416 KB
testcase_18	AC	159 ms; 28,416 KB
testcase_19	AC	163 ms; 28,400 KB
testcase_20	AC	160 ms; 28,416 KB
testcase_21	AC	159 ms; 28,544 KB
testcase_22	AC	159 ms; 28,288 KB
testcase_23	AC	160 ms; 28,416 KB
testcase_24	AC	160 ms; 28,452 KB
testcase_25	AC	160 ms; 28,380 KB
testcase_26	AC	1,111 ms; 28,368 KB
testcase_27	AC	914 ms; 28,288 KB
testcase_28	AC	1,082 ms; 28,520 KB
testcase_29	AC	1,054 ms; 28,352 KB
testcase_30	AC	1,086 ms; 28,488 KB
testcase_31	AC	161 ms; 28,288 KB
testcase_32	AC	160 ms; 28,288 KB
testcase_33	AC	165 ms; 28,288 KB
testcase_34	AC	161 ms; 28,544 KB
testcase_35	AC	162 ms; 28,516 KB
testcase_36	AC	7 ms; 5,376 KB
testcase_37	AC	7 ms; 5,376 KB
testcase_38	AC	7 ms; 5,376 KB
testcase_39	AC	7 ms; 5,376 KB
testcase_40	AC	6 ms; 5,376 KB
testcase_41	TLE	-

ソースコード

#pragma region satashun
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;

using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
template <class T>
using V = vector<T>;
template <class T>
using VV = V<V<T>>;

template <class T>
V<T> make_vec(size_t a) {
    return V<T>(a);
}

template <class T, class... Ts>
auto make_vec(size_t a, Ts... ts) {
    return V<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define rep(i, n) rep2(i, 0, n)
#define rep2(i, m, n) for (int i = m; i < (n); i++)
#define per(i, b) per2(i, 0, b)
#define per2(i, a, b) for (int i = int(b) - 1; i >= int(a); i--)
#define ALL(c) (c).begin(), (c).end()
#define SZ(x) ((int)(x).size())

constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n - 1); }

template <class T, class U>
void chmin(T &t, const U &u) {
    if (t > u) t = u;
}
template <class T, class U>
void chmax(T &t, const U &u) {
    if (t < u) t = u;
}

template <class T>
void mkuni(vector<T> &v) {
    sort(ALL(v));
    v.erase(unique(ALL(v)), end(v));
}

template <class T>
vector<int> sort_by(const vector<T> &v, bool increasing = true) {
    vector<int> res(v.size());
    iota(res.begin(), res.end(), 0);

    if (increasing) {
        stable_sort(res.begin(), res.end(),
                    [&](int i, int j) { return v[i] < v[j]; });
    } else {
        stable_sort(res.begin(), res.end(),
                    [&](int i, int j) { return v[i] > v[j]; });
    }
    return res;
}

template <class T, class U>
istream &operator>>(istream &is, pair<T, U> &p) {
    is >> p.first >> p.second;
    return is;
}

template <class T, class U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
    os << "(" << p.first << "," << p.second << ")";
    return os;
}

template <class T>
istream &operator>>(istream &is, vector<T> &v) {
    for (auto &x : v) {
        is >> x;
    }
    return is;
}

template <class T>
ostream &operator<<(ostream &os, const vector<T> &v) {
    os << "{";
    rep(i, v.size()) {
        if (i) os << ",";
        os << v[i];
    }
    os << "}";
    return os;
}

#ifdef LOCAL
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
    cerr << " " << H;
    debug_out(T...);
}
#define debug(...) \
    cerr << __LINE__ << " [" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#define dump(x) cerr << __LINE__ << " " << #x << " = " << (x) << endl
#else
#define debug(...) (void(0))
#define dump(x) (void(0))
#endif

template <class T>
void scan(vector<T> &v, T offset = T(0)) {
    for (auto &x : v) {
        cin >> x;
        x += offset;
    }
}

// suc : 1 = newline, 2 = space
template <class T>
void print(T x, int suc = 1) {
    cout << x;
    if (suc == 1)
        cout << "\n";
    else if (suc == 2)
        cout << " ";
}

template <class T>
void print(const vector<T> &v, int suc = 1) {
    for (int i = 0; i < v.size(); ++i)
        print(v[i], i == int(v.size()) - 1 ? suc : 2);
}

template <class T>
void show(T x) {
    print(x, 1);
}

template <typename Head, typename... Tail>
void show(Head H, Tail... T) {
    print(H, 2);
    show(T...);
}

struct prepare_io {
    prepare_io() {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(10);
    }
} prep_io;
#pragma endregion satashun

// intersectSP modified on 2018/7/5

namespace geom {

#define X real()
#define Y imag()
#define at(i) ((*this)[i])
#define EPS (1e-9)
#define PI (3.1415926535897932384626)

using R = long double;
using P = complex<R>;

inline int sgn(R a, R b = 0) { return a < b - EPS ? -1 : a > b + EPS ? 1 : 0; }
inline bool near(P a, P b) { return !sgn(abs(a - b)); }
inline R norm(const P &p) { return p.X * p.X + p.Y * p.Y; }
inline R dot(const P &a, const P &b) { return real(a * conj(b)); }
inline R cross(const P &a, const P &b) { return imag(conj(a) * b); }
inline R sr(R a) { return sqrt(max(a, (R)0)); }
inline P unit(const P &p) { return p / abs(p); }
inline P proj(const P &s, const P &t) { return t * dot(s, t) / norm(t); }

struct L : public vector<P> {  // line
    L() {}
    L(const P &a, const P &b) {
        this->push_back(a);
        this->push_back(b);
    }
    P dir() const { return at(1) - at(0); }
};

struct G : public vector<P> {
    G(int sz = 0) : vector(sz) {}
    L edge(int i) const { return L(at(i), at(i + 1 == size() ? 0 : i + 1)); }
};

//(a->b->c)
int ccw(P a, P b, P c) {
    b -= a;
    c -= a;
    R cr = cross(b, c);
    if (sgn(cr) > 0) return 1;                 // counter clockwise
    if (sgn(cr) < 0) return -1;                // clockwise
    if (sgn(dot(b, c)) < 0) return 2;          // c--a--b on line
    if (sgn(norm(b), norm(c)) < 0) return -2;  // a--b--c on line
    return 0;
}

// L..line, S..segment, P..point

bool intersectLL(const L &l, const L &m) {
    return abs(cross(l[1] - l[0], m[1] - m[0])) > EPS ||  // non-parallel
           abs(cross(l[1] - l[0], m[0] - l[0])) < EPS;    // same line
}

bool intersectLS(const L &l, const L &s) {
    return cross(l[1] - l[0], s[0] - l[0]) *  // s[0] is left of l
               cross(l[1] - l[0], s[1] - l[0]) <
           EPS;  // s[1] is right of l
}

bool intersectLP(const L &l, const P &p) {
    return abs(cross(l[1] - p, l[0] - p)) < EPS;
}

bool intersectSS(const L &s, const L &t) {
    return ccw(s[0], s[1], t[0]) * ccw(s[0], s[1], t[1]) <= 0 &&
           ccw(t[0], t[1], s[0]) * ccw(t[0], t[1], s[1]) <= 0;
}

bool intersectSP(const L &s, const P &p) { return !ccw(s[0], s[1], p); }

inline P proj(const P &s, const L &t) {
    return t[0] + proj(s - t[0], t[1] - t[0]);
}

P projection(const L &l, const P &p) {
    R t = dot(p - l[0], l[0] - l[1]) / norm(l[0] - l[1]);
    return l[0] + t * (l[0] - l[1]);
}

P reflection(const L &l, const P &p) {
    return p + (projection(l, p) - p) * (R)2;
}

R distanceLP(const L &l, const P &p) { return abs(p - projection(l, p)); }

R distanceLL(const L &l, const L &m) {
    return intersectLL(l, m) ? 0 : distanceLP(l, m[0]);
}

R distanceLS(const L &l, const L &s) {
    if (intersectLS(l, s)) return 0;
    return min(distanceLP(l, s[0]), distanceLP(l, s[1]));
}

R distanceSP(const L &s, const P &p) {
    const P r = projection(s, p);
    if (intersectSP(s, r)) return abs(r - p);
    return min(abs(s[0] - p), abs(s[1] - p));
}

R distanceSS(const L &s, const L &t) {
    if (intersectSS(s, t)) return 0;
    return min(min(distanceSP(s, t[0]), distanceSP(s, t[1])),
               min(distanceSP(t, s[0]), distanceSP(t, s[1])));
}

P crosspoint(const L &l, const L &m) {
    R A = cross(l[1] - l[0], m[1] - m[0]);
    R B = cross(l[1] - l[0], l[1] - m[0]);
    if (abs(A) < EPS && abs(B) < EPS) return m[0];  // same line
    if (abs(A) < EPS) assert(false);  // !!!PRECONDITION NOT SATISFIED!!!
    return m[0] + B / A * (m[1] - m[0]);
}

struct C {
    P c;
    R r;
};

pair<P, P> crosspoint(C a, C b) {
    R d = abs(a.c - b.c);
    R l = ((a.r * a.r - b.r * b.r) / d + d) / 2.0;
    R h = sqrt(a.r * a.r - l * l);
    P e = a.c + (b.c - a.c) * l / d;
    P p = (b.c - a.c) * h / d * P(0, -1);
    return make_pair(e + p, e - p);
}

pair<P, P> crosspoint(C c, L l) {
    P p = projection(l, c.c);
    R d = abs(p - c.c);
    P ve = unit(l.dir());
    R w = sr(c.r * c.r - d * d);
    return mp(p - w * ve, p + w * ve);
}

R area(P a, P b, P c) { return imag(conj(b - a) * (c - a)) * 0.5; }

#define curr(P, i) P[i]
#define next(P, i) P[(i + 1) % P.size()]

R poly_area(const G &vec) {
    R ret = 0.0;
    rep(i, vec.size()) ret += cross(curr(vec, i), next(vec, i));
    return fabs(ret) / (R)2;
}

// center of mass
P center(const G &vec) {
    R ar = 0;
    P c(0, 0);
    rep(i, vec.size()) {
        P a = curr(vec, i), b = next(vec, i);
        R t = a.X * b.Y - b.X * a.Y;
        ar += t;
        c += (a + b) * t;
    }
    c /= 3 * ar;
    return c;
}

// polygon,point
enum { OUT, ON, IN };
int contains(const G &vec, const P &p) {
    bool in = false;
    for (int i = 0; i < vec.size(); ++i) {
        P a = curr(vec, i) - p, b = next(vec, i) - p;
        if (imag(a) > imag(b)) swap(a, b);
        if (imag(a) <= 0 && 0 < imag(b))
            if (cross(a, b) < 0) in = !in;
        if (cross(a, b) == 0 && dot(a, b) <= 0) return ON;
    }
    return in ? IN : OUT;
}

/* 精密
 enum { TRUE = 1, FALSE = 0, BORDER = -1 };

 int contains(const G& vec, const P &p) {
 R sum = .0;
 rep(i, vec.size()) {
        L l(curr(vec, i), next(vec, i));
        if (intersectSP(l, p)) return BORDER;
        sum += arg((curr(vec, i) - p) / (next(vec, i) - p));
 }
 return !!sgn(sum);
 }
 */

bool containSG(const L &s, const G &vec) {
    vector<P> p;
    p.push_back(s[0]);
    p.push_back(s[1]);

    for (int i = 0; i < vec.size(); ++i) {
        L e(vec[i], vec[(i + 1) % vec.size()]);

        if (abs(cross(e[1] - e[0], s[1] - s[0])) > EPS) {
            if (intersectSS(e, s)) p.push_back(crosspoint(e, s));
        }

        if (intersectSP(s, vec[i])) p.push_back(vec[i]);
    }

    sort(ALL(p));

    for (int i = 0; i < (int)p.size() - 1; ++i) {
        P pt = (p[i] + p[i + 1]) / R(2);
        if (contains(vec, pt) == OUT) return false;
    }

    return true;
}

G convex_cut(const G &Pl, const L &l) {
    G Q;
    for (int i = 0; i < Pl.size(); ++i) {
        P A = curr(Pl, i), B = next(Pl, i);
        if (ccw(l[0], l[1], A) != -1) Q.push_back(A);
        if (ccw(l[0], l[1], A) * ccw(l[0], l[1], B) < 0)
            Q.push_back(crosspoint(L(A, B), l));
    }
    return Q;
}

G convex_hull(G ps) {
    int n = ps.size(), k = 0;
    sort(ALL(ps), [&](const P &a, const P &b) {
        return sgn(a.X - b.X) ? a.X < b.X : a.Y < b.Y;
    });

    G ch(2 * n);

    for (int i = 0; i < n; ch[k++] = ps[i++])  // lower-hull
        while (k >= 2 && ccw(ch[k - 2], ch[k - 1], ps[i]) <= 0) --k;
    for (int i = n - 2, t = k + 1; i >= 0; ch[k++] = ps[i--])  // upper-hull
        while (k >= t && ccw(ch[k - 2], ch[k - 1], ps[i]) <= 0) --k;
    ch.resize(k - 1);
    return ch;
}

struct DualGraph {
    struct DEdge {
        int u, v, f, l;
        R a;
        DEdge(int u, int v, R a) : u(u), v(v), f(0), l(0) {
            while (PI < a) a -= 2 * PI;
            while (a < -PI) a += 2 * PI;
            this->a = a;
        }
        bool operator==(const DEdge &opp) const { return v == opp.v; }
        bool operator<(const DEdge &opp) const { return a > opp.a; }
        bool operator<(const R &opp) const { return a > opp; }
    };

    int n;
    vector<P> p;
    vector<vector<DEdge>> g;
    DualGraph(const vector<P> &p) : p(p), g(p.size()), n(p.size()) {}

    void add_edge(int s, int t) {
        R a = arg(p[t] - p[s]);
        g[s].emplace_back(s, t, a);
        g[t].emplace_back(t, s, a + PI);
    }
    vector<G> poly;

    void add_polygon(int s, int t, R a) {
        auto e = lower_bound(ALL(g[s]), a - EPS);
        if (e == g[s].end()) e = g[s].begin();
        if (e->f) return;
        e->f = 1;
        e->l = t;
        poly[t].push_back(p[s]);
        add_polygon(e->v, t, e->a > 0 ? e->a - PI : e->a + PI);
    }

    vector<G> &dual() {
        rep(i, n) {
            sort(ALL(g[i]));
            g[i].erase(unique(ALL(g[i])), g[i].end());
        }

        int s = min_element(ALL(p)) - p.begin();
        poly.emplace_back();
        add_polygon(s, poly.size() - 1, -PI * (R).5);

        rep(i, n) rep(j, g[i].size()) if (!g[i][j].f) {
            poly.emplace_back();
            add_polygon(i, poly.size() - 1, g[i][j].a + 2. * EPS);
        }
        return poly;
    }
};

template <class T>
void merge(vector<T> &s) {
    rep(i, s.size()) if (s[i][1] < s[i][0]) swap(s[i][0], s[i][1]);
    sort(ALL(s));

    rep(i, s.size())
        rep(j, i) if (!sgn(cross(s[i][1] - s[i][0], s[j][1] - s[j][0])) &&
                      intersectSS(s[i], s[j])) {
        s[j][1] = max(s[i][1], s[j][1]);
        s.erase(s.begin() + i--);
        break;
    }
}

struct Arrangement {
    struct AEdge {
        int u, v, t;
        R cost;
        AEdge() {}
        AEdge(int u = 0, int v = 0, int t = 0, R cost = 0)
            : u(u), v(v), t(t), cost(cost) {}
    };

    typedef vector<vector<AEdge>> AGraph;
    vector<P> p;
    AGraph g;
    Arrangement() {}

    Arrangement(vector<L> &seg) {
        merge(seg);
        int m = seg.size();

        rep(i, m) {
            p.push_back(seg[i][0]);
            p.push_back(seg[i][1]);
            rep(j, i) if (sgn(cross(seg[i][1] - seg[i][0],
                                    seg[j][1] - seg[j][0]) &&
                              intersectSS(seg[i], seg[j])))
                p.push_back(crosspoint(seg[i], seg[j]));
        }

        sort(ALL(p));
        p.erase(unique(ALL(p)), p.end());

        int n = p.size();
        g.resize(n);

        rep(i, m) {
            L &s = seg[i];
            vector<pair<R, int>> ps;
            rep(j, n) if (intersectSP(s, p[j]))
                ps.emplace_back(norm(p[j] - s[0]), j);
            sort(ALL(ps));

            rep(j, (int)ps.size() - 1) {
                const int u = ps[j].second;
                const int v = ps[j + 1].second;
                g[u].emplace_back(u, v, 0, abs(p[u] - p[v]));
                g[v].emplace_back(v, u, 0, abs(p[u] - p[v]));
            }
        }
    }
};

}  // namespace geom

using namespace geom;

namespace std {
bool operator<(const P &a, const P &b) {
    return sgn(a.X - b.X) ? a.X < b.X : a.Y < b.Y;
}
istream &operator>>(istream &is, P &p) {
    R x, y;
    is >> x >> y;
    p = P(x, y);
    return is;
}
}  // namespace std

void slv() {
    int N;
    cin >> N;
    ll ans = 0;

    G pl(N);
    cin >> pl;

    auto hull = convex_hull(pl);

    V<P> vec;
    for (auto p : hull) {
        for (auto q : hull) {
            ll ar = abs(cross(p, q));
            chmax(ans, ar);
        }
    }
    show(ans);
}

int main() {
    int cases = 1;
    // cin >> cases;
    rep(i, cases) slv();

    return 0;
}