#778446 (C++17) No.2009 Drunkers' Contest

提出ソース

結果

問題	No.2009 Drunkers' Contest
ユーザー	satashun
提出日時	2022-07-15 22:01:09
言語	C++17 (gcc 13.2.0 + boost 1.83.0)
結果	AC
実行時間	95 ms / 2,000 ms
コード長	11,108 bytes
コンパイル時間	2,751 ms
コンパイル使用メモリ	220,928 KB
実行使用メモリ	36,528 KB
最終ジャッジ日時	2023-09-10 01:49:12
合計ジャッジ時間	8,428 ms
ジャッジサーバーID （参考情報）	judge13 / judge11

このコードへのチャレンジ（β）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 4,380 KB
testcase_01	AC	1 ms 4,384 KB
testcase_02	AC	1 ms 4,376 KB
testcase_03	AC	1 ms 4,376 KB
testcase_04	AC	1 ms 4,380 KB
testcase_05	AC	1 ms 4,376 KB
testcase_06	AC	2 ms 4,380 KB
testcase_07	AC	2 ms 4,376 KB
testcase_08	AC	1 ms 4,380 KB
testcase_09	AC	2 ms 4,380 KB
testcase_10	AC	2 ms 4,380 KB
testcase_11	AC	2 ms 4,380 KB
testcase_12	AC	1 ms 4,380 KB
testcase_13	AC	2 ms 4,380 KB
testcase_14	AC	2 ms 4,380 KB
testcase_15	AC	3 ms 4,376 KB
testcase_16	AC	3 ms 4,376 KB
testcase_17	AC	3 ms 4,380 KB
testcase_18	AC	3 ms 4,380 KB
testcase_19	AC	4 ms 4,380 KB
testcase_20	AC	3 ms 4,380 KB
testcase_21	AC	4 ms 4,380 KB
testcase_22	AC	4 ms 4,376 KB
testcase_23	AC	4 ms 4,380 KB
testcase_24	AC	95 ms 34,816 KB
testcase_25	AC	93 ms 34,544 KB
testcase_26	AC	94 ms 35,476 KB
testcase_27	AC	94 ms 34,708 KB
testcase_28	AC	94 ms 34,584 KB
testcase_29	AC	94 ms 34,456 KB
testcase_30	AC	93 ms 35,156 KB
testcase_31	AC	93 ms 34,692 KB
testcase_32	AC	94 ms 34,464 KB
testcase_33	AC	94 ms 34,872 KB
testcase_34	AC	89 ms 35,332 KB
testcase_35	AC	89 ms 36,052 KB
testcase_36	AC	91 ms 35,308 KB
testcase_37	AC	91 ms 35,032 KB
testcase_38	AC	90 ms 35,196 KB
testcase_39	AC	90 ms 35,056 KB
testcase_40	AC	89 ms 34,804 KB
testcase_41	AC	89 ms 34,672 KB
testcase_42	AC	90 ms 34,684 KB
testcase_43	AC	90 ms 35,008 KB
testcase_44	AC	94 ms 34,552 KB
testcase_45	AC	93 ms 35,848 KB
testcase_46	AC	80 ms 34,704 KB
testcase_47	AC	73 ms 36,012 KB
testcase_48	AC	74 ms 35,452 KB
testcase_49	AC	73 ms 34,416 KB
testcase_50	AC	74 ms 34,824 KB
testcase_51	AC	75 ms 36,528 KB
testcase_52	AC	75 ms 35,108 KB
testcase_53	AC	82 ms 34,884 KB
testcase_54	AC	81 ms 34,632 KB
testcase_55	AC	81 ms 35,060 KB
testcase_56	AC	81 ms 36,028 KB
testcase_57	AC	80 ms 35,088 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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;
    ch.resize(k);
    return ch;
}

}  // 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;
    V<ll> A(N), B(N);
    cin >> A >> B;

    G pts;
    pts.eb(0, 0);

    V<ll> sa(N + 1), sb(N + 1);

    rep(i, N) {
        sa[i + 1] = sa[i] + A[i];
        sb[i + 1] = sb[i] + B[i];
        pts.eb(sb[i + 1], sa[i + 1]);
    }

    auto hull = convex_hull(pts);

    for (auto p : hull) {
        debug(p.X, p.Y);
    }

    double sx = 0, sy = 0;
    double ans = 0.0;
    double t = 1.0;

    for (int i = 1; i < hull.size(); ++i) {
        double nt = max<double>(t, sqrt((hull[i].Y - sy) / (hull[i].X - sx)));
        ans += ((hull[i].Y - sy) / nt + (hull[i].X - sx) * nt);
        sx = hull[i].X;
        sy = hull[i].Y;
        t = nt;
    }
    show(ans);
}

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

    return 0;
}

yukicoder

結果

テストケース

ソースコード