← Real problems

cco04p4

easysimulationgeometryStatement on DMOJ

CP Lang

14 lines0.3 spec
// cco04p4: two walkers repeat their scripts of unit steps forever. Both return to the same
// phase after lcm(len_s, len_t) steps, so the closest approach happens within one joint period.
fn walker() -> (at: Pt, steps: List<Pt>):
    let (x, y, n) = read<(Int, Int, 0..=10_000)>()
    let moves = read<[n](d: Int, axis: Char)>()
    let unit = (m: (d: Int, axis: Char)) => if m.axis == 'X': Pt(Int(sign(m.d)), 0) else: Pt(0, Int(sign(m.d)))
    (Pt(x, y), moves.flat_map(m => [unit(m) for _ in 0..abs(m.d)]).collect())
var (s, t) = (walker(), walker())
var best = s.at.dist(t.at)
for i in 0..lcm(s.steps.len, t.steps.len):
    s.at += s.steps[i % s.steps.len]
    t.at += t.steps[i % t.steps.len]
    best min= s.at.dist(t.at)
print(best, precision: 2)

Accepted C++

103 lines · 1.33 s on the judge
#include "bits/extc++.h"

using namespace std;

template <typename T>
void dbgh(const T& t) {
    cerr << t << endl;
}

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
    cerr << t << " | ";
    dbgh(u...);
}

#ifdef DEBUG
#define dbg(...)                                           \
    cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]" \
         << ": ";                                          \
    dbgh(__VA_ARGS__)
#else
#define cerr   \
    if (false) \
    cerr
#define dbg(...)
#endif

using ld = long double;

#define endl "\n"
#define long int64_t
#define sz(x) int(std::size(x))

template <typename T>
vector<T> repeat(const vector<T>& arr, int kv) {
    vector<T> ans;
    for (int i = 0; i < kv; i++) {
        ans.insert(ans.end(), begin(arr), end(arr));
    }
    return ans;
}

template <typename T>
T sign(T x) {
    return (x > 0) - (x < 0);
}

tuple<int, int, vector<pair<int, int>>> read() {
    int sx, sy, n;
    cin >> sx >> sy >> n;
    vector<pair<int, int>> ans;
    for (int i = 0; i < n; i++) {
        int d, x, y;
        char c;
        cin >> d >> c;
        if (!d) {
            continue;
        }
        if (c == 'X') {
            x = sign(d);
            y = 0;
        } else {
            y = sign(d);
            x = 0;
        }
        for (int j = 0; j < abs(d); j++) {
            ans.emplace_back(x, y);
        }
    }
    return {sx, sy, ans};
}

void solve() {
    auto [sx, sy, sarr] = read();
    auto [tx, ty, tarr] = read();
    ld ans = 1e100;
    int si = 0, ti = 0;
    do {
        auto upd = [&](int& x, int& y, const pair<int, int>& p) -> void {
            auto& [dx, dy] = p;
            x += dx;
            y += dy;
        };
        ans = min(ans, hypotl(sx - tx, sy - ty));
        upd(sx, sy, sarr[si++]);
        upd(tx, ty, tarr[ti++]);
        if (si == sz(sarr)) {
            si = 0;
        }
        if (ti == sz(tarr)) {
            ti = 0;
        }
    } while (si || ti);
    cout << ans << endl;
}

int main() {
    cin.tie(nullptr);
    cin.exceptions(ios::failbit);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(2);
    solve();
}