#1170590 (C++23) No.2594 Mix shake!!

• 問題: No.2594 Mix shake!!
• ユーザー: hitonanode
• 提出日時: 2026-07-08 22:15:37
• 言語: C++23 (gcc 15.2.0 + boost 1.90.0)
• 結果: AC
• 実行時間: 51 ms / 2,000 ms
• コード長: 3,829 bytes
• コンパイル時間: 10,219 ms
• コンパイル使用メモリ: 627,652 KB
• 実行使用メモリ: 9,264 KB
• 最終ジャッジ日時: 2026-07-08 22:15:57
• 合計ジャッジ時間: 13,134 ms
• ジャッジサーバーID （参考情報）: judge2_1 / judge3_0

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

ソースコード

#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>
using namespace std;

using boost::multiprecision::cpp_rational;
using Rat = cpp_rational;

struct Item {
    long long a, b;
    int id;
};

struct Point {
    Rat x, y;
};

// b / a の昇順
bool cmp_item(const Item& u, const Item& v) {
    __int128 lhs = (__int128)u.b * v.a;
    __int128 rhs = (__int128)v.b * u.a;

    if (lhs != rhs) return lhs < rhs;
    if (u.a != v.a) return u.a < v.a;
    if (u.b != v.b) return u.b < v.b;
    return u.id < v.id;
}

vector<Point> cumulative(const vector<Item>& v) {
    vector<Point> p;
    Rat x = 0, y = 0;
    p.push_back({x, y});

    for (auto &e : v) {
        x += Rat(e.a);
        y += Rat(e.b);
        p.push_back({x, y});
    }

    return p;
}

// 目標の折れ線が初期の折れ線より下を通っていないか
bool final_not_below_initial(const vector<Point>& low, const vector<Point>& up) {
    int n = (int)low.size() - 1;

    for (int i = 0; i < n; i++) {
        Rat x0 = low[i].x, y0 = low[i].y;
        Rat x1 = low[i + 1].x, y1 = low[i + 1].y;

        Rat dx = x1 - x0;
        Rat dy = y1 - y0;

        for (auto &p : up) {
            Rat cross = dx * (p.y - y0) - dy * (p.x - x0);
            if (cross < 0) return false;
        }
    }

    return true;
}

// low と up の間を max_seg 本以下の線分からなる折れ線で結べるか
bool can_between_with_segments(
    const vector<Point>& low,
    const vector<Point>& up,
    int max_seg
) {
    Rat goal_x = low.back().x;

    Rat px = 0;
    Rat py = 0;

    int used = 0;

    while (px < goal_x) {
        used++;
        if (used > max_seg) return false;

        bool has = false;
        Rat slope = 0;

        // 現在点から出て、up を超えない最大の傾き
        for (auto &q : up) {
            if (px < q.x) {
                Rat s = (q.y - py) / (q.x - px);
                if (!has || s < slope) slope = s;
                has = true;
            }
        }

        if (!has) return true;

        bool found = false;

        // その傾きの半直線が low と次に交わる点まで進む
        for (int i = 0; i + 1 < (int)low.size(); i++) {
            Point a = low[i];
            Point b = low[i + 1];

            if (!(px < b.x)) continue;

            Rat slope_to_b = (b.y - py) / (b.x - px);

            if (!(slope < slope_to_b)) continue;

            Rat seg_slope = (b.y - a.y) / (b.x - a.x);

            Rat diff = (b.y - py) - slope * (b.x - px);

            Rat nx = b.x - diff / (seg_slope - slope);
            Rat ny = py + slope * (nx - px);

            px = nx;
            py = ny;

            found = true;
            break;
        }

        // low ともう交わらないなら終点まで進める
        if (!found) break;
    }

    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<long long> a(n), b(n), c(n), d(n);

    for (auto &x : a) cin >> x;
    for (auto &x : b) cin >> x;
    for (auto &x : c) cin >> x;
    for (auto &x : d) cin >> x;

    vector<Item> init, target;

    for (int i = 0; i < n; i++) {
        init.push_back({a[i], b[i], i});
        target.push_back({c[i], d[i], i});
    }

    sort(init.begin(), init.end(), cmp_item);
    sort(target.begin(), target.end(), cmp_item);

    vector<Point> low = cumulative(init);
    vector<Point> up = cumulative(target);

    if (!final_not_below_initial(low, up)) {
        cout << "No\n";
        return 0;
    }

    bool same_order = true;
    for (int i = 0; i < n; i++) {
        if (init[i].id != target[i].id) same_order = false;
    }

    if (same_order || can_between_with_segments(low, up, n - 1)) {
        cout << "Yes\n";
    } else {
        cout << "No\n";
    }

    return 0;
}