結果

問題 No.2012 Largest Triangle
ユーザー satashun
提出日時 2022-07-15 22:49:21
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 14,094 bytes
コンパイル時間 2,652 ms
コンパイル使用メモリ 226,084 KB
最終ジャッジ日時 2025-01-30 08:38:18
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 40 TLE * 1
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0