結果

問題 No.3100 Parallel Translated
ユーザー rogi52
提出日時 2025-04-11 22:08:50
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 18,325 bytes
コンパイル時間 3,787 ms
コンパイル使用メモリ 294,800 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2025-04-11 22:08:58
合計ジャッジ時間 4,581 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff # 

#line 2 "/Users/korogi/Desktop/cp-cpp/template.hpp"
#include <bits/stdc++.h>
using namespace std;

using i32 = int;
using i64 = long long;
using i128 = __int128;
using u32 = unsigned int;
using u64 = unsigned long long;
using u128 = unsigned __int128;
using f32 = double;
using f64 = long double;
using f128 = __float128;

#define DMP(x) cout << "[" << __LINE__ << "]" << " " << #x << ":" << " " << x << endl;

#define FOR1(n)          for(int _ =  0 , n_ = (n); _ < n_; _++)
#define FOR2(i, n)       for(int i =  0 , n_ = (n); i < n_; i++)
#define FOR3(i, s, t)    for(int i = (s), t_ = (t); i < t_; i++)
#define FOR4(i, s, t, d) for(int i = (s), t_ = (t), d_ = (d); i < t_; i += d_)
#define OVERLOAD4(a, b, c, d, e, ...) e
#define FOR(...) OVERLOAD4(__VA_ARGS__, FOR4, FOR3, FOR2, FOR1)(__VA_ARGS__)

#define REV1(n)          for(int _ = (n) - 1; _ >=  0 ; _--)
#define REV2(i, n)       for(int i = (n) - 1; i >=  0 ; i--)
#define REV3(i, s, t)    for(int i = (t) - 1, s_ = (s); i >= s_; i--)
#define REV4(i, s, t, d) for(int i = (t) - 1, s_ = (s), d_ = (d); i >= s_; i -= d_)
#define OVERLOAD3(a, b, c, d, ...) d
#define REV(...) OVERLOAD4(__VA_ARGS__, REV4, REV3, REV2, REV1)(__VA_ARGS__)

#define FOR_SUBSET(T, S) for(int S_ = (S), T = S_; T >= 0; T = (T == 0 ? -1 : (T - 1) & S_))

#define MULTI for(int testcase_ = in(), testcase = 0; testcase < testcase_; testcase++) [&]

template < class T > using heap_max = priority_queue< T, vector< T >, less< T > >;
template < class T > using heap_min = priority_queue< T, vector< T >, greater< T >>;

template < class T, class U > bool chmin(T& a, const U& b) { return a > b ? a = b, 1 : 0; }
template < class T, class U > bool chmax(T& a, const U& b) { return a < b ? a = b, 1 : 0; }

i64 floor_div(const i64 n, const i64 d) { assert(d != 0); return n / d - ((n ^ d) <  0 && n % d != 0); }
i64  ceil_div(const i64 n, const i64 d) { assert(d != 0); return n / d + ((n ^ d) >= 0 && n % d != 0); }

template < class T, class F > T bin_search(T ok, T ng, F check) { while(abs(ok - ng) > 1) { T mid = (ok + ng) / 2; (check(mid) ? ok : ng) = mid; } return ok; }
template < class T, class F > T bin_search_real(T ok, T ng, F check, int step = 100) { FOR(step) { T mid = (ok + ng) / 2; (check(mid) ? ok : ng) = mid; } return ok; }

template < class T, class U > T accum(const vector< U >& a) { return accumulate(a.begin(), a.end(), T(0)); }
template < class T > pair< T, int > min(const vector< T >& a) { auto itr = min_element(a.begin(), a.end()); return {*itr, itr - a.begin()}; }
template < class T > pair< T, int > max(const vector< T >& a) { auto itr = max_element(a.begin(), a.end()); return {*itr, itr - a.begin()}; }
template < class T > void sort(vector< T >& a) { sort(a.begin(), a.end()); }
template < class T > void rsort(vector< T >& a) { sort(a.rbegin(), a.rend()); }
template < class T > void reverse(vector< T >& a) { reverse(a.begin(), a.end()); }
void sort(string& s) { sort(s.begin(), s.end()); }
void rsort(string& s) { sort(s.rbegin(), s.rend()); }
void reverse(string& s) { reverse(s.begin(), s.end()); }
template < class T, class Cmp > void sort(vector< T >& a, Cmp cmp) { sort(a.begin(), a.end(), cmp); }
template < class T > int LB(vector< T >& a, T x) { return distance(a.begin(), lower_bound(a.begin(), a.end(), x)); }
template < class T > int UB(vector< T >& a, T x) { return distance(a.begin(), upper_bound(a.begin(), a.end(), x)); }
template < class T > void unique(vector< T >& a) { sort(a.begin(), a.end()); a.erase(unique(a.begin(), a.end()), a.end()); }
vector<int> iota(int n) { vector<int> a(n); iota(a.begin(), a.end(), 0); return a; }

istream& operator >> (istream& is, i128& x) {
    string s; is >> s;
    int m = (s[0] == '-');
    x = 0;
    FOR(i, m, ssize(s)) x = x * 10 + (s[i] - '0');
    if(m) x *= -1;
    return is;
}
ostream& operator << (ostream& os, const i128& x) {
    if(x == 0) return os << '0';
    i128 y = x; if(y < 0) { os << '-'; y *= -1; }
    vector<int> ny;
    while(y) ny.push_back(y % 10), y /= 10;
    REV(i, ssize(ny)) os << ny[i];
    return os;
}
namespace scan {
struct x0 { template < class T > operator T() { T x; cin >> x; return x; } };
struct x1 { int n; x1(int n) : n(n) {} template < class T > operator vector< T >() { vector< T > a(n); for(T& x : a) cin >> x; return a; } };
struct x2 { int h, w; x2(int h, int w) : h(h), w(w) {} template < class T > operator vector< vector< T > >() { vector m(h, vector< T >(w)); for(vector< T >& a : m) for(T& x : a) cin >> x; return m; } };
struct cppio { cppio() { cin.tie(0); ios::sync_with_stdio(0); } } cppio_instance;
}
scan::x0 in() { return scan::x0(); }
scan::x1 in(int n) { return scan::x1(n); }
scan::x2 in(int h, int w) { return scan::x2(h, w); }

template < class T > ostream& operator << (ostream& os, const vector< T > a) {
    const int n = a.size();
    FOR(i, n) { os << a[i]; if(i + 1 != n) os << ' '; }
    return os;
}
template < class T > int print_n(const vector< T > a) { for(T x : a) cout << x << '\n'; return 0; }
int print() { cout << '\n'; return 0; }
template < class Head, class... Tail > int print(Head&& h, Tail&&... t) { cout << h; if(sizeof...(Tail)) cout << ' '; return print(forward<Tail>(t)...); }
namespace printer {
    void prec(int n) { cout << fixed << setprecision(n); }
    void flush() { cout.flush(); }
}

constexpr pair<int, int> dir4[] = {{-1, 0}, {0, -1}, {+1, 0}, {0, +1}};

vector<int>& operator ++ (vector<int>& a) { for(auto& e : a) e++; return a; }
vector<int>& operator -- (vector<int>& a) { for(auto& e : a) e--; return a; }
vector<int>  operator ++ (vector<int>& a, int) { vector<int> b = a; ++a; return b; }
vector<int>  operator -- (vector<int>& a, int) { vector<int> b = a; --a; return b; }

template < class T > vector<pair< T, int>> RLE(const vector< T >& a) { vector<pair< T, int>> v; for(const T& x : a) { if(not v.empty() and v.back().first == x) v.back().second++; else v.emplace_back(x, 1); } return v; }
vector<pair<char, int>> RLE(const string& s) { vector<pair<char, int>> v; for(const char& c : s) { if(not v.empty() and v.back().first == c) v.back().second++; else v.emplace_back(c, 1); } return v; }
template < class String, class Same > vector<String> RLE(const String& a, const Same same) { vector<String> v; for(const auto& x : a) { if(not v.empty() and same(v.back().back(), x)) v.back().push_back(x); else v.push_back({x}); } return v; }

int YESNO(bool yes) { return print(yes ? "YES" : "NO"); }
int YesNo(bool yes) { return print(yes ? "Yes" : "No"); }

constexpr i32 INF32 = 1e9;
constexpr i64 INF64 = 1e18;
#line 3 "/Users/korogi/Desktop/cp-cpp/mod/modint.hpp"

template < u32 mod_, u32 prime_, u32 root_ > struct static_modint {
    static constexpr u32 const & mod = mod_;
    static constexpr u32 const & prime = prime_;
    static constexpr u32 const & root = root_;
    u32 v;
    using mint = static_modint;
    constexpr mint& s(u32 v) { this->v = v < mod ? v : v - mod; return *this; }
    constexpr static_modint(i64 v = 0) { s(v % mod + mod); }
    mint operator - () const { return mint() - *this; }
    mint operator + () const { return *this; }
    mint& operator += (const mint& r) { return s(v + r.v); }
    mint& operator -= (const mint& r) { return s(v + mod - r.v); }
    mint& operator *= (const mint& r) { v = u64(v) * r.v % mod; return *this; }
    mint& operator /= (const mint& r) { return *this *= inv(r); }
    mint operator + (const mint& r) const { return mint(*this) += r; }
    mint operator - (const mint& r) const { return mint(*this) -= r; }
    mint operator * (const mint& r) const { return mint(*this) *= r; }
    mint operator / (const mint& r) const { return mint(*this) /= r; }
    bool operator == (const mint& r) const { return v == r.v; }
    bool operator != (const mint& r) const { return v != r.v; }
};
// x^n
template < u32 mod, u32 prime, u32 root > static_modint<mod, prime, root> pow(static_modint<mod, prime, root> x, u64 n) {
    static_modint<mod, prime, root> p(1);
    for(; n; n >>= 1) { if(n & 1) p *= x; x *= x; }
    return p;
}
// x^{-1}
template < u32 mod, u32 prime, u32 root > static_modint<mod, prime, root> inv(static_modint<mod, prime, root> x) {
    int a = x.v, b = mod, u = 1, v = 0;
    while(b) { int t = a / b; swap(a -= t * b, b); swap(u -= t * v, v); }
    return static_modint<mod, prime, root>(u);
}
template < u32 mod, u32 prime, u32 root > istream& operator >> (istream& is, static_modint<mod, prime, root>& x) { i64 v; is >> v; x = static_modint<mod, prime, root>(v); return is; }
template < u32 mod, u32 prime, u32 root > ostream& operator << (ostream& os, const static_modint<mod, prime, root>& x) { return os << x.v; }

using modint998 = static_modint<  998'244'353, 1, 3>;
using modint107 = static_modint<1'000'000'007, 1, 5>;
#line 3 "a.cpp"
using mint = modint998;
#line 2 "/Users/korogi/Desktop/cp-cpp/mod/binom.hpp"

template < class mint > mint fact(int n) {
    static const u32 mod = mint::mod;
    assert(0 <= n); assert(n < mod); assert(mint::prime);
    static vector<mint> data = {1, 1};
    while(ssize(data) <= n) { const int i = ssize(data); data.push_back(data.back() * i); }
    return data[n];
}
template < class mint > mint inv(int n) {
    static const u32 mod = mint::mod;
    assert(0 <= n); assert(n < mod); assert(mint::prime);
    static vector<mint> data = {1, 1};
    while(ssize(data) <= n) { const int i = ssize(data); data.push_back(-data[mod % i] * (mod / i)); }
    return data[n];
}
template < class mint > mint fact_inv(int n) {
    static const u32 mod = mint::mod;
    assert(0 <= n); assert(n < mod); assert(mint::prime);
    static vector<mint> data = {1, 1};
    while(ssize(data) <= n) { const int i = ssize(data); data.push_back(data.back() * inv<mint>(i)); }
    return data[n];
}
template < class mint > mint comb(int n, int k) {
    return 0 <= k and k <= n ? fact<mint>(n) * fact_inv<mint>(k) * fact_inv<mint>(n - k) : 0;
}

template < class T > struct powers {
    T a; vector< T > data;
    powers(const T a) : a(a), data({1}) {}
    // a^n
    T get(int n) {
        assert(0 <= n);
        while(ssize(data) <= n) data.push_back(data.back() * a);
        return data[n];
    }
};
#line 5 "a.cpp"

template < class T > struct point {
    T x, y;
    point() : x(0), y(0) {}
    point(T x, T y) : x(x), y(y) {}
    point(std::pair< T, T > p) : x(p.first), y(p.second) {}
    point& operator+=(const point& p) { x += p.x, y += p.y; return *this; }
    point& operator-=(const point& p) { x -= p.x, y -= p.y; return *this; }
    point& operator*=(const T r) { x *= r, y *= r; return *this; }
    point& operator/=(const T r) { x /= r, y /= r; return *this; }
    point operator+(const point& p) const { return point(*this) += p; }
    point operator-(const point& p) const { return point(*this) -= p; }
    point operator*(const T r) const { return point(*this) *= r; }
    point operator/(const T r) const { return point(*this) /= r; }
    point operator-() const { return {-x, -y}; }
    bool operator==(const point& p) const { return x == p.x and y == p.y; }
    bool operator!=(const point& p) const { return x != p.x or  y != p.y; }
    bool operator<(const point& p) const { return x == p.x ? y < p.y : x < p.x; }
    point< T > rot(double theta) {
        static_assert(is_floating_point_v< T >);
        double cos_ = std::cos(theta), sin_ = std::sin(theta);
        return {cos_ * x - sin_ * y, sin_ * x + cos_ * y};
    }
};
template < class T > istream& operator>>(istream& is, point< T >& p) { return is >> p.x >> p.y; }
template < class T > ostream& operator<<(ostream& os, point< T >& p) { return os << p.x << " " << p.y; }
template < class T > T dot(const point< T >& a, const point< T >& b) { return a.x * b.x + a.y * b.y; }
template < class T > T det(const point< T >& a, const point< T >& b) { return a.x * b.y - a.y * b.x; }
template < class T > T norm(const point< T >& p) { return p.x * p.x + p.y * p.y; }
template < class T > double abs(const point< T >& p) { return std::sqrt(norm(p)); }
template < class T > double angle(const point< T >& p) { return std::atan2(p.y, p.x); }
template < class T > int sign(const T x) {
    T e = (is_integral_v< T > ? 1 : 1e-8);
    if(x <= -e) return -1;
    if(x >= +e) return +1;
    return 0;
}
template < class T > bool equals(const T& a, const T& b) { return sign(a - b) == 0; }
template < class T > int ccw(const point< T >& a, point< T > b, point< T > c) {
    b -= a, c -= a;
    if(sign(det(b, c)) == +1) return +1; // counter clockwise
    if(sign(det(b, c)) == -1) return -1; //         clockwise
    if(sign(dot(b, c)) == -1) return +2; // c-a-b
    if(norm(b) < norm(c)) return -2;     // a-b-c
    return 0;                            // a-c-b
}

template < class T > struct line {
    point< T > a, b;
    line() {}
    line(point< T > a, point< T > b) : a(a), b(b) {}
};
template < class T > point< T > projection(const line< T >& l, const point< T >& p) {
    static_assert(is_floating_point_v< T >);
    return l.a + (l.a - l.b) * dot(p - l.a, l.a - l.b) / norm(l.a - l.b);
}
template < class T > point< T > reflection(const line< T >& l, const point< T >& p) {
    static_assert(is_floating_point_v< T >);
    return p + (projection(l, p) - p) * T(2);
}
template < class T > bool orthogonal(const line< T >& a, const line< T >& b) { return equals(dot(a.b - a.a, b.b - b.a), T(0)); }
template < class T > bool parallel  (const line< T >& a, const line< T >& b) { return equals(det(a.b - a.a, b.b - b.a), T(0)); }
template < class T > point< T > cross_point_ll(const line< T >& l, const line< T >& m) {
    static_assert(is_floating_point_v< T >);
    T A = det(l.b - l.a, m.b - m.a);
    T B = det(l.b - l.a, l.b - m.a);
    if(equals(abs(A), T(0)) and equals(abs(B), T(0))) return m.a;
    return m.a + (m.b - m.a) * B / A;
}

template < class T > using segment = line< T >;
template < class T > bool intersect_ss(const segment< T >& s, const segment< T >& t) {
    return ccw(s.a, s.b, t.a) * ccw(s.a, s.b, t.b) <= 0 and ccw(t.a, t.b, s.a) * ccw(t.a, t.b, s.b) <= 0;
}
template < class T > double distance_sp(const segment< T >& s, const point< T >& p) {
    static_assert(is_floating_point_v< T >);
    point r = projection(s, p);
    if(ccw(s.a, s.b, r) == 0) return abs(r - p);
    return std::min(abs(s.a - p), abs(s.b - p));
}
template < class T > double distance_ss(const segment< T >& a, const segment< T >& b) {
    if(intersect_ss(a, b)) return 0;
    return std::min({ distance_sp(a, b.a), distance_sp(a, b.b), distance_sp(b, a.a), distance_sp(b, a.b) });
}

template < class T > using polygon = std::vector< point< T > >;
template < class T > T area2(const polygon< T >& p) {
    T s = 0;
    int n = p.size();
    for(int i = 0; i < n; i++) s += det(p[i], p[(i + 1) % n]);
    return s;
}
template < class T > T area(const polygon< T >& p) { return area2(p) / T(2); }

template < class T > bool is_convex(const polygon< T >& p) {
    int n = p.size();
    for(int i = 0; i < n; i++) if(ccw(p[(i - 1 + n) % n], p[i], p[(i + 1) % n]) == -1) return false;
    return true;
}
template < class T > int contains(const polygon< T >& g, const point< T >& p) {
    int n = g.size();
    bool in = false;
    for(int i = 0; i < n; i++) {
        point a = g[i] - p, b = g[(i + 1) % n] - p;
        if(sign(a.y - b.y) == +1) std::swap(a, b);
        if(sign(a.y) <= 0 and sign(b.y) ==+1 and sign(det(a, b)) == -1) in = !in;
        if(sign(det(a, b)) == 0 and sign(dot(a, b)) <= 0) return 1; // ON
    }
    return in ? 2 : 0;
}
template < class T > polygon< T > convex_cut(const polygon< T >& p, const line< T >& l) {
    int n = p.size();
    polygon< T > res;
    for(int i = 0; i < n; i++) {
        point now = p[i], nxt = p[(i + 1) % n];
        if(ccw(l.a, l.b, now) != -1) res.push_back(now);
        if(ccw(l.a, l.b, now) * ccw(l.a, l.b, nxt) < 0) res.push_back(cross_point_ll(line(now, nxt), l));
    }
    return res;
}
template < class T > polygon< T > convex_hull(polygon< T >& p) {
    int n = p.size(), k = 0;
    if(n <= 2) return p;
    std::sort(p.begin(), p.end());
    polygon< T > ch(n + n);
    for(int i = 0; i < n; ch[k++] = p[i++])
        while(k >= 2 and sign(det(ch[k - 1] - ch[k - 2], p[i] - ch[k - 1])) == -1) k--;
    for(int i = n - 2, t = k + 1; i >= 0; ch[k++] = p[i--])
        while(k >= t and sign(det(ch[k - 1] - ch[k - 2], p[i] - ch[k - 1])) == -1) k--;
    ch.resize(k - 1);
    return ch;
}
template < class T > T diameter2(const polygon< T >& p) {
    static_assert(is_floating_point_v< T >);
    int n = p.size(), is = 0, js = 0;
    for(int i = 1; i < n; i++) {
        if(sign(p[i].y - p[is].y) == +1) is = i;
        if(sign(p[i].y - p[js].y) == -1) js = i;
    }
    T dist_max = norm(p[is] - p[js]);
    int maxi = is, i = is, maxj = js, j = js;
    do {
        if(sign(det(p[(i + 1) % n] - p[i], p[(j + 1) % n] - p[j])) >= 0) j = (j + 1) % n; else i = (i + 1) % n;
        if(norm(p[i] - p[j]) > dist_max) {
            dist_max = norm(p[i] - p[j]);
            maxi = i, maxj = j;
        }
    } while(i != is or j != js);
    return dist_max;
}
template < class T > double diameter(const polygon< T >& p) {
    static_assert(is_floating_point_v< T >);
    return std::sqrt(diameter2(p));
}

template < class T > struct circle {
    point< T > p;
    T r;
    circle() = default;
    circle(point< T > p, T r) : p(p), r(r) {}
};
template < class T > istream& operator>>(istream& is, circle< T >& c) { return is >> c.p >> c.r; }
template < class T > int intersect_cc(circle< T > c1, circle< T > c2) {
    if(c1.r < c2.r) std::swap(c1, c2);
    T d = abs(c1.p - c2.p);
    if(sign(c1.r + c2.r - d) == -1) return 4;
    if(equals(c1.r + c2.r, d)) return 3;
    if(sign(c1.r - c2.r - d) == -1) return 2;
    if(equals(c1.r - c2.r, d)) return 1;
    return 0;
}
template < class T > std::pair<point< T >, point< T >> cross_point_cc(const circle< T >& c1, const circle< T >& c2) {
    T d = abs(c1.p - c2.p);
    T a = std::acos((c1.r * c1.r + d * d - c2.r * c2.r) / (2 * c1.r * d));
    T t = angle(c2.p - c1.p);
    point< T > p1 = c1.p + point< T >(std::cos(t + a), std::sin(t + a)) * c1.r;
    point< T > p2 = c1.p + point< T >(std::cos(t - a), std::sin(t - a)) * c1.r;
    return {p1, p2};
}

int main() {
    int N = in();
    vector<point<i64>> P(N);
    FOR(i, N) P[i].x = in(), P[i].y = in();
    print(mint(area2(P)) / 2);
}
0