#1176551 (C++23(gcc16)) No.1447 Greedy MtSaka

• 問題: No.1447 Greedy MtSaka
• ユーザー: shuphy129
• 提出日時: 2026-08-13 15:14:09
• 言語: C++23(gcc16) (gcc 16.1.0 + boost 1.90.0)
• 結果: AC
• 実行時間: 1 ms / 2,000 ms
• コード長: 14,976 bytes
• コンパイル時間: 2,454 ms
• コンパイル使用メモリ: 356,148 KB
• 実行使用メモリ: 5,888 KB
• 最終ジャッジ日時: 2026-08-13 15:14:13
• 合計ジャッジ時間: 3,379 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge2_0

ファイルパターン	結果
sample	AC * 3
other	AC * 17

ソースコード

#ifndef ONLINE_JUDGE
#define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>
using namespace std;
using ll = long long; // 9e18 = 9*10^18
using ull = unsigned long long;
using ld = long double;
/*
#include <atcoder/all>
using namespace atcoder;
*/
/*
#include <atcoder/modint>
using namespace atcoder;
//using mint = modint; // mint::set_mod(MOD);
//using mint = modint1000000007;
using mint = modint998244353;
std::ostream &operator<< (std::ostream &os, mint x){ // mintデバッグ出力用
    os << x.val(); return os;
}
*/
#define rep(i, n) for(ll i=0; i<(n); ++i)       //  0  => n-1 [0-index]
#define rep1(i, n) for(ll i=1; i<=(n); ++i)     //  1  =>  n  [1-index]
#define drep(i, n) for(ll i=(n)-1; i>=0; --i)   // n-1 =>  0  [0-index]
#define drep1(i, n) for(ll i=(n); i>0; --i)     //  n  =>  1  [1-index]
#define repa(i, a, n) for(ll i=(a); i<(n); ++i) //  a  => n-1
#define el '\n' // フラッシュはendlを使う
#define YES cout << "Yes" << endl
#define NO  cout << "No" << endl
#define ERR cout << -1 << endl
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define fi first
#define se second
#define len(v) ((int)(v).size())
#define cout_double cout << fixed << setprecision(20)
inline ll ceil_int(const ll a, const ll b){ // doubleキャスト不要の切り上げ
    if(a >= 0) return (a + b - 1) / b;
    return a / b;
}
inline ll floor_int(const ll a, const ll b){ // doubleキャスト不要の切り捨て
    if(a % b < 0) return (a / b) - 1;
    return a / b;
}
ll isqrt(ll n){ // floor(sqrt(n))を求める
    if(n <= 0) return 0;
    ll x = sqrt(n);
    while((x + 1) * (x + 1) <= n) ++x;
    while(x * x > n) --x;
    return x;
}
inline ll sum_ap(const ll a, const ll l, const ll n){ // 等差数列の和 (初項, 末項, 項数)
    return (a + l) * n / 2;
}
inline ll nc2(const ll n){ return n * (n - 1) / 2; }
inline ll nc3(const ll n){ return n * (n - 1) * (n - 2) / 6; }
template <class T>
inline bool chmax(T &a, const T &b){
    if(a < b){ a = b; return true; }
    return false;
}
template <class T>
inline bool chmin(T &a, const T &b){
    if(b < a){ a = b; return true; }
    return false;
}
template <class T>
inline void unique_erase(vector<T> &v){ // 配列をソートしユニークな値だけ残す
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
}
inline string substr_head(const string &s, int n){ // 文字列の先頭n文字を切り出す
    int s_len = s.size();
    if(n > s_len) n = s_len; // sの文字数を超えないように調整される
    return s.substr(0, n);
}
inline string substr_tail(const string &s, int n){ // 文字列の末尾n文字を切り出す
    int s_len = s.size();
    if(n > s_len) n = s_len; // sの文字数を超えないように調整される
    return s.substr(s_len - n);
}
template <class T>
using vc = vector<T>; // vc<int> = vector<int>
template <class T>
using vv = vector<vector<T>>;
template <class T>
using vvv = vector<vector<vector<T>>>;
template <class T, int n, size_t idx = 0> // 多次元vector生成
auto make_vc(const int (&d)[n], const T &init) noexcept {
    if constexpr (idx < n) return vector(d[idx], make_vc<T, n, idx+1>(d, init));
    else return init;
} // auto v = make_vc<int>({2, 3}, 0);
template <class T, int n>
auto make_vc(const int (&d)[n]) noexcept {
    return make_vc(d, T{});
}
template <class T>
using dheap = priority_queue<T>; // 降順優先度付きキュー
template <class T>
using uheap = priority_queue<T, vector<T>, greater<>>; // 昇順優先度付きキュー
template <class T1, class T2> // pairの出力 cout << pair << el
std::ostream &operator<< (std::ostream &os, std::pair<T1,T2> p){
    os << "{" << p.first << ", " << p.second << "}";
    return os;
}
template <class T> // 1次元配列の出力関数 第2引数trueで改行区切り
inline void print_vc(const vector<T> &v, bool split_line = false) {
    if (v.empty()) { cout << '\n'; return; }
    for (int i = 0; i < (int)v.size(); ++i) {
        cout << v[i] << " \n"[split_line || i + 1 == (int)v.size()];
    }
}
template <class T> // 2次元配列の出力関数 第2引数trueでidx表示
void print_vv(const vector<vector<T>> &vv, bool idx_print = false){
    if (vv.empty()) { cout << '\n'; return; }
    for (int i = 0; i < (int)vv.size(); ++i) {
        if(idx_print) cout << i << ": ";
        print_vc(vv[i]);
    }
}
template<class... T> // 可変引数 入力
void IN(T&... a){ (cin >> ... >> a); }
void OUT(){ cout << endl; }
template<class T, class... Ts> // 可変引数 空白区切り出力
void OUT(const T& a, const Ts&... b){
    cout << a;
    if constexpr (sizeof...(b) > 0){ cout << ' '; }
    OUT(b...);
}
template <class T, class... Ts> // デバッグ出力用
void OUT_DBG(std::string_view name, const T& a, Ts&&... b){
    const auto end = name.find_first_of(',');
    cout << name.substr(0, end) << ": " << a;
    if constexpr (sizeof...(b) > 0){
        cout << " | ";
        OUT_DBG(name.substr(name.find_first_not_of(' ', end + 1)), std::forward<Ts>(b)...);
    }
}
/* デバッグ出力 */
#ifndef ONLINE_JUDGE
#define MEMO(s) cout << "\033[31m" << s << " \033[m"     // 改行なし
#define MEMO_el(s) cout << "\033[31m" << s << "\033[m\n" // 改行あり
#define DBG(...)                                      \
    {                                                 \
        cout << "\033[33m(line:" << __LINE__ << ") "; \
        OUT_DBG(#__VA_ARGS__, __VA_ARGS__);           \
        cout << "\033[m\n";                           \
    }
#define DBG_vc(v)                                     \
    {                                                 \
        cout << "\033[33m(line:" << __LINE__ << ") "  \
        << #v  << "(" << (int)v.size() << "):\n";     \
        print_vc(v); cout << "\033[m";                \
    } // 1次元配列
#define DBG_vv(vv)                                    \
    {                                                 \
        cout << "\033[33m(line:" << __LINE__ << ") "  \
        << #vv << "(" << (int)vv.size() << "):\n";    \
        print_vv(vv, true); cout << "\033[m";         \
    } // 2次元配列
#define DBG_st(st)                                    \
    {                                                 \
        cout << "\033[33m(line:" << __LINE__ << ") "  \
        << #st << "(" << (int)st.size() << "):\n";    \
        for(auto e : st) { cout << e << ' '; }        \
        cout << "\033[m\n";                           \
    } // set multiset rope
constexpr bool DEBUG = true;
#else
#define MEMO(s) do {} while(0)
#define MEMO_el(s) do {} while(0)
#define DBG(...) do {} while(0)
#define DBG_vc(v) do {} while(0)
#define DBG_vv(vv) do {} while(0)
#define DBG_st(st) do {} while(0)
constexpr bool DEBUG = false;
#endif
const int INF = 2e9;  // 2*10^9
//const int INF = 1'073'741'823; // 2倍する場合
const ll INFL = 2e18; // 2*10^18
/* =========================================== */

/* 基本群 */

// https://github.com/maspypy/library/blob/main/geo/base.hpp
/* 2次元座標 */
template <class T>
struct Point {
    T x, y;

    // コンストラクタ
    Point() : x(0), y(0) {}

    template <class A, class B>
    Point(A x, B y) : x(x), y(y) {}

    template <class A, class B>
    Point(pair<A, B> p) : x(p.fi), y(p.se) {}

    template <class U>
    Point(Point<U> p) : x(p.x), y(p.y) {}

    // cinでx, yの順に入力を受け取る
    friend std::istream& operator>>(std::istream &is, Point &p){
        is >> p.x >> p.y;
        return is;
    }

    // ベクトル演算
    Point operator+(Point p) const { return {x + p.x, y + p.y}; }
    Point operator-(Point p) const { return {x - p.x, y - p.y}; }
    Point operator-() const { return {-x, -y}; }
    Point operator*(T t) const { return {x * t, y * t}; }
    Point operator/(T t) const { return {x / t, y / t}; }
    bool operator==(Point p) const { return x == p.x && y == p.y; }
    bool operator!=(Point p) const { return x != p.x || y != p.y; }
    bool operator<(Point p) const {
        if (x != p.x) return x < p.x;
        return y < p.y;
    }

    // ベクトル演算&更新
    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;
    }

    // a.dot(b) = aとbの内積
    T dot(const Point& other) const { return x * other.x + y * other.y; }
    // a.det(b) = aとbの外積 +:左回り -:右回り 0:一直線
    T det(const Point& other) const { return x * other.y - y * other.x; }

    T abs_int() { return (x * x + y * y); } // ベクトルの大きさの2乗
    long double abs() { return sqrtl(x * x + y * y); } // ベクトルの大きさ
    long double angle() { return atan2l(y, x); } // 偏角(ラジアン)

    // theta回転 整数型非対応
    Point rotate(double theta) {
        static_assert(!is_integral<T>::value);
        double c = cos(theta), s = sin(theta);
        return Point{c * x - s * y, s * x + c * y};
    }
    // 90度回転 ccw = true:反時計回り false:時計回り
    Point rot90(bool ccw) { return (ccw ? Point{-y, x} : Point{y, -x}); }
};

/* A -> B -> C と進むときに、左に曲がるならば +1、右に曲がるならば -1 */
template <class T>
int ccw(Point<T> A, Point<T> B, Point<T> C) {
    T x = (B - A).det(C - A);
    if (x > 0) return 1;  // 左に曲がる
    if (x < 0) return -1; // 右に曲がる
    return 0;             // 一直線(Uターン含む)
}

/* 2点間の距離 */
template <class T> // 2乗値
T dist_int(Point<T> A, Point<T> B){
    T dx = A.x - B.x;
    T dy = A.y - B.y;
    return (dx * dx + dy * dy);
}
// dist<double>(a, b)
template <class REAL, class T, class U>
REAL dist(Point<T> A, Point<U> B) {
    REAL dx = REAL(A.x) - REAL(B.x);
    REAL dy = REAL(A.y) - REAL(B.y);
    return sqrt(dx * dx + dy * dy);
}

/* 直線 ax+by+cの形 */
template <class T>
struct Line {
    T a, b, c;

    // コンストラクタ
    Line(T a, T b, T c) : a(a), b(b), c(c) {}
    Line(Point<T> A, Point<T> B) {
        a = A.y - B.y;
        b = B.x - A.x;
        c = A.x * B.y - A.y * B.x;
    }
    Line(T x1, T y1, T x2, T y2) : Line(Point<T>(x1, y1), Point<T>(x2, y2)) {}

    template <class U> // 点と直線の位置関係
    U eval(Point<U> P) { // 戻り値0: 座標Pが直線上にある
        return U(a) * P.x + U(b) * P.y + U(c);
    }
    template <class U>
    T eval(U x, U y) {
        return a * x + b * y + c;
    }

    // 正規化 同じ直線が同じ a,b,c で表現されるようにする
    void normalize() {
        static_assert(is_same_v<T, int> || is_same_v<T, long long>);
        T g = gcd(gcd(abs(a), abs(b)), abs(c));
        a /= g, b /= g, c /= g;
        if (b < 0) {
        a = -a, b = -b, c = -c;
        }
        if (b == 0 && a < 0) {
        a = -a, b = -b, c = -c;
        }
    }

    // 平行ならtrue
    bool is_parallel(Line other) { return a * other.b - b * other.a == 0; }
    // 垂直ならtrue
    bool is_orthogonal(Line other) { return a * other.a + b * other.b == 0; }
    // 同じ直線ならtrue
    bool is_same(Line other) {
        if (a * other.b != b * other.a) return false;
        if (a * other.c != c * other.a) return false;
        if (b * other.c != c * other.b) return false;
        return true;
    }
    bool operator==(Line other) const { return is_same(other); }
    bool operator!=(Line other) const { return is_same(other); }
};

/* 線分 */
template <class T>
struct Segment {
    Point<T> A, B;

    Segment(Point<T> A, Point<T> B) : A(A), B(B) {}
    Segment(T x1, T y1, T x2, T y2)
        : Segment(Point<T>(x1, y1), Point<T>(x2, y2)) {}

    bool contain(Point<T> C) { // 戻り値true: 座標Cが線分上にある
        T det = (C - A).det(B - A);
        if (det != 0) return false;
        return (C - A).dot(B - A) >= 0 && (C - B).dot(A - B) >= 0;
    }

    // 線分を直線に変換
    Line<T> to_Line() { return Line(A, B); }
};

/* 円 */
template <class T>
struct Circle {
    Point<T> O; // 中心
    T r; // 半径

    Circle() {}
    Circle(Point<T> O, T r) : O(O), r(r) {}
    Circle(T x, T y, T r) : O(x, y), r(r) {}

    bool operator==(Circle other) const { return O == other.O && r == other.r; }
    bool operator!=(Circle other) const { return O != other.O || r != other.r; }

    template <class U> // 点と円の位置関係 その1
    bool contain(Point<U> p) { // 戻り値true: 座標pが円の内部(境界含む)
        T dx = p.x - O.x, dy = p.y - O.y;
        return dx * dx + dy * dy <= r * r;
    }

    template <class U> // 点と円の位置関係 詳細
    int eval(Point<U> p) {
        T dx = p.x - O.x, dy = p.y - O.y;
        if(dx * dx + dy * dy < r * r) return 0; // 0: 内包する
        if(dx * dx + dy * dy == r * r) return 1; // 1: 円周上
        return 2; // 2: 外部
    }

    template <class U> // 円と円の交点の個数
    int common_point(Circle<U> other) {
        if(O == other.O && r == other.r) return 3; // 3(INF)個: 完全一致
        T dx = other.O.x - O.x, dy = other.O.y - O.y;
        if(dx * dx + dy * dy < (other.r - r) * (other.r - r))  return 0;  // 0個: 内包する
        if(dx * dx + dy * dy == (other.r - r) * (other.r - r)) return 1; // 1: 内接する(完全一致含む)
        if(dx * dx + dy * dy < (other.r + r) * (other.r + r))  return 2;  // 2: 2点で交わる
        if(dx * dx + dy * dy == (other.r + r) * (other.r + r)) return 1; // 1: 外接する
        return 0;  // 0個: 外部
    }

    template <class U> // 円と円の位置関係 詳細
    int eval(Circle<U> other) {
        T dx = other.O.x - O.x, dy = other.O.y - O.y;
        if(dx * dx + dy * dy < (other.r - r) * (other.r - r))  return 0;  // 0: 内包する
        if(dx * dx + dy * dy == (other.r - r) * (other.r - r)) return 1; // 1: 内接する(完全一致含む)
        if(dx * dx + dy * dy < (other.r + r) * (other.r + r))  return 2;  // 2: 2点で交わる
        if(dx * dx + dy * dy == (other.r + r) * (other.r + r)) return 3; // 3: 外接する
        return 4;  // 4: 外部
    }
};

using P = Point<ll>;

/* 未検証 */
/* 多角形の面積の2倍値 凸でなくてもよい */
// https://perogram.hateblo.jp/entry/2020/09/25/032842
// 引数はPoint型の配列(要素数3以上)
ll polygon_area(vector<P> v){
    ll n = v.size();
    v.push_back(v[0]); // 頂点を1周してくるので最初と最後に同じ頂点を置く
    ll ret = 0;
    P g = {0, 0}; // 原点
    rep(i, n){
        P a = v[i] - g;
        P b = v[i+1] - g;
        ret += a.det(b); // 外積
    }
    ret = abs(ret);
    return ret;
}

int main(){
    // ios::sync_with_stdio(false);
	// cin.tie(nullptr);
    int n;
    cin >> n;
    vc<P> point(n);
    rep(i, n){
        cin >> point[i];
    }
    reverse(all(point)); // 実験

    cout << polygon_area(point) << el;
    return 0;
}

/*
Ctrl + /
Shift + Alt + A
*/