結果

問題 No.1932 動く点 P / Moving Point P
ユーザー ForestedForested
提出日時 2022-05-06 22:27:25
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,644 ms / 6,000 ms
コード長 10,973 bytes
コンパイル時間 2,613 ms
コンパイル使用メモリ 138,908 KB
実行使用メモリ 210,488 KB
最終ジャッジ日時 2023-09-20 03:27:31
合計ジャッジ時間 27,905 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,380 KB
testcase_01 AC 519 ms
107,288 KB
testcase_02 AC 357 ms
107,204 KB
testcase_03 AC 576 ms
16,072 KB
testcase_04 AC 793 ms
55,056 KB
testcase_05 AC 640 ms
54,896 KB
testcase_06 AC 173 ms
55,364 KB
testcase_07 AC 1,623 ms
210,488 KB
testcase_08 AC 1,644 ms
210,288 KB
testcase_09 AC 1,125 ms
210,416 KB
testcase_10 AC 1,141 ms
210,368 KB
testcase_11 AC 1,139 ms
210,368 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

// ===== template.hpp =====
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

#define OVERRIDE(a, b, c, d, ...) d
#define REP2(i, n) for (i32 i = 0; i < (i32) (n); ++i)
#define REP3(i, m, n) for (i32 i = (i32) (m); i < (i32) (n); ++i)
#define REP(...) OVERRIDE(__VA_ARGS__, REP3, REP2)(__VA_ARGS__)
#define PER(i, n) for (i32 i = (i32) (n) - 1; i >= 0; --i)
#define ALL(x) begin(x), end(x)

using namespace std;

using u32 = unsigned int;
using u64 = unsigned long long;
using u128 = __uint128_t;
using i32 = signed int;
using i64 = signed long long;
using i128 = __int128_t;

template <typename T>
using Vec = vector<T>;

template <typename T>
bool chmin(T &x, const T &y) {
    if (x > y) {
        x = y;
        return true;
    }
    return false;
}
template <typename T>
bool chmax(T &x, const T &y) {
    if (x < y) {
        x = y;
        return true;
    }
    return false;
}

istream &operator>>(istream &is, i128 &x) {
    i64 v;
    is >> v;
    x = v;
    return is;
}
ostream &operator<<(ostream &os, i128 x) {
    os << (i64) x;
    return os;
}
istream &operator>>(istream &is, u128 &x) {
    u64 v;
    is >> v;
    x = v;
    return is;
}
ostream &operator<<(ostream &os, u128 x) {
    os << (u64) x;
    return os;
}

template <typename F, typename Comp = less<>>
Vec<i32> sort_index(i32 n, F f, Comp comp = Comp()) {
    Vec<i32> idx(n);
    iota(ALL(idx), 0);
    sort(ALL(idx), [&](i32 i, i32 j) -> bool {
        return comp(f(i), f(j));
    });
    return idx;
}

[[maybe_unused]] constexpr i32 INF = 1000000100;
[[maybe_unused]] constexpr i64 INF64 = 3000000000000000100;

struct FastIO {
    FastIO() {
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
        cout << fixed << setprecision(10);
    }
} fast_io;
// ===== template.hpp =====

#ifdef DEBUGF
#include  "../new_library/other/debug.hpp"
#else
#define DBG(x) (void) 0
#endif

// ===== segment_tree.hpp =====
#ifndef SEGMENT_TREE_HPP
#define SEGMENT_TREE_HPP

#include <cassert>
#include <utility>
#include <vector>

// ===== operations.hpp =====
#ifndef OPERATIONS_HPP
#define OPERATIONS_HPP

#include <limits>
#include <utility>

template <typename T>
struct Add {
    using Value = T;
    static Value id() {
        return T(0);
    }
    static Value op(const Value &lhs, const Value &rhs) {
        return lhs + rhs;
    }
    static Value inv(const Value &x) {
        return -x;
    }
};

template <typename T>
struct Mul {
    using Value = T;
    static Value id() {
        return Value(1);
    }
    static Value op(const Value &lhs, const Value &rhs) {
        return lhs * rhs;
    }
    static Value inv(const Value &x) {
        return Value(1) / x;
    }
};

template <typename T>
struct Min {
    using Value = T;
    static Value id() {
        return std::numeric_limits<T>::max();
    }
    static Value op(const Value &lhs, const Value &rhs) {
        return std::min(lhs, rhs);
    }
};

template <typename T>
struct Max {
    using Value = T;
    static Value id() {
        return std::numeric_limits<Value>::min();
    }
    static Value op(const Value &lhs, const Value &rhs) {
        return std::max(lhs, rhs);
    }
};

template <typename T>
struct Xor {
    using Value = T;
    static Value id() {
        return T(0);
    }
    static Value op(const Value &lhs, const Value &rhs) {
        return lhs ^ rhs;
    }
    static Value inv(const Value &x) {
        return x;
    }
};

template <typename Monoid>
struct Reversible {
    using Value = std::pair<typename Monoid::Value, typename Monoid::Value>;
    static Value id() {
        return Value(Monoid::id(), Monoid::id());
    }
    static Value op(const Value &v1, const Value &v2) {
        return Value(
            Monoid::op(v1.first, v2.first),
            Monoid::op(v2.second, v1.second));
    }
};

#endif
// ===== operations.hpp =====

template <typename Monoid>
class SegmentTree {
public:
    using Value = typename Monoid::Value;

private:
    std::size_t old_length;
    std::size_t length;
    std::vector<Value> node;

    static std::size_t ceil2(std::size_t n) {
        std::size_t l = 1;
        while (l < n) {
            l <<= 1;
        }
        return l;
    }

public:
    SegmentTree(std::size_t n) :
        old_length(n),
        length(ceil2(old_length)),
        node(length << 1, Monoid::id()) {}

    SegmentTree(const std::vector<Value> &v) :
        old_length(v.size()),
        length(ceil2(old_length)),
        node(length << 1, Monoid::id()) {
        for (std::size_t i = 0; i < old_length; ++i) {
            node[i + length] = v[i];
        }
        for (std::size_t i = length - 1; i > 0; --i) {
            node[i] = Monoid::op(node[i << 1], node[i << 1 | 1]);
        }
    }

    template <typename F>
    SegmentTree(std::size_t n, const F &f) :
        old_length(n), length(ceil2(n)), node(length << 1, Monoid::id()) {
        for (std::size_t i = 0; i < old_length; ++i) {
            node[i + length] = f(i);
        }
        for (std::size_t i = length - 1; i > 0; --i) {
            node[i] = Monoid::op(node[i << 1], node[i << 1 | 1]);
        }
    }

    const Value &operator[](std::size_t idx) const {
        assert(idx < old_length);
        return node[idx + length];
    }

    void update(std::size_t idx, Value val) {
        assert(idx < old_length);
        idx += length;
        node[idx] = std::move(val);
        while (idx != 1) {
            idx >>= 1;
            node[idx] = Monoid::op(node[idx << 1], node[idx << 1 | 1]);
        }
    }

    Value prod(std::size_t l, std::size_t r) const {
        assert(l <= r && r <= old_length);
        Value prodl = Monoid::id();
        Value prodr = Monoid::id();
        l += length;
        r += length;
        while (l != r) {
            if (l & 1) {
                prodl = Monoid::op(prodl, node[l++]);
            }
            if (r & 1) {
                prodr = Monoid::op(node[--r], prodr);
            }
            l >>= 1;
            r >>= 1;
        }
        return Monoid::op(prodl, prodr);
    }
    
    Value all_prod() const {
        return node[1];
    }
};

#endif
// ===== segment_tree.hpp =====
// ===== matrix.hpp =====
#ifndef MATRIX_HPP
#define MATRIX_HPP

#include <vector>
#include <cassert>
#include <utility>

template <typename T>
class Matrix {
    std::vector<std::vector<T>> val;
    
public:
    Matrix() : val() {}
    Matrix(std::size_t h, std::size_t w) : val(h, std::vector<T>(w)) {}
    Matrix(std::size_t h, std::size_t w, const T &ele) : val(h, std::vector<T>(w, ele)) {}
    Matrix(std::vector<std::vector<T>> _val) : val(std::move(_val)) {}
    
    std::size_t row() const {
        return val.size();
    }
    
    std::size_t column() const {
        return val[0].size();
    }
    
    T &operator()(std::size_t i, std::size_t j) {
        return val[i][j];
    }
    const T &operator()(std::size_t i, std::size_t j) const {
        return val[i][j];
    }
    
    Matrix<T> operator+() const {
        return *this;
    }
    Matrix<T> operator-() const {
        Matrix<T> ret(row(), column());
        for (std::size_t i = 0; i < row(); ++i) {
            for (std::size_t j = 0; j < column(); ++j) {
                ret.val[i][j] = -val[i][j];
            }
        }
        return ret;
    }
    
    Matrix<T> &operator+=(const Matrix &rhs) {
        assert(row() == rhs.row() && column() == rhs.column());
        for (std::size_t i = 0; i < row(); ++i) {
            for (std::size_t j = 0; j < column(); ++j) {
                val[i][j] += rhs.val[i][j];
            }
        }
        return *this;
    }
    friend Matrix<T> operator+(Matrix<T> lhs, const Matrix<T> &rhs) {
        return lhs += rhs;
    }
    
    Matrix<T> &operator-=(const Matrix &rhs) {
        assert(row() == rhs.row() && column() == rhs.column());
        for (std::size_t i = 0; i < row(); ++i) {
            for (std::size_t j = 0; j < column(); ++j) {
                val[i][j] -= rhs.val[i][j];
            }
        }
        return *this;
    }
    friend Matrix<T> operator-(Matrix<T> lhs, const Matrix<T> &rhs) {
        return lhs += rhs;
    }
    
    Matrix<T> &operator*=(const Matrix<T> &rhs) {
        *this = *this * rhs;
        return *this;
    }
    friend Matrix<T> operator*(const Matrix<T> &lhs, const Matrix<T> &rhs) {
        assert(lhs.column() == rhs.row());
        Matrix<T> ret(lhs.row(), rhs.column());
        for (std::size_t i = 0; i < lhs.row(); ++i) {
            for (std::size_t j = 0; j < rhs.column(); ++j) {
                for (std::size_t k = 0; k < lhs.column(); ++k) {
                    ret.val[i][j] += lhs.val[i][k] * rhs.val[k][j];
                }
            }
        }
        return ret;
    }
    
    static Matrix<T> ident(std::size_t n) {
        Matrix<T> ret(n, n, T(0));
        for (std::size_t i = 0; i < n; ++i) {
            ret.val[i][i] = T(1);
        }
        return ret;
    }
    
    void swap_rows(std::size_t i, std::size_t j) {
        std::swap(val[i], val[j]);
    }
    void swap_columns(std::size_t i, std::size_t j) {
        for (std::vector<T> &row : val) {
            std::swap(row[i], row[j]);
        }
    }
};

#endif
// ===== matrix.hpp =====

struct Ops {
    using Value = Matrix<double>;
    static Value id() {
        return Value::ident(3);
    }
    static Value op(const Value &x, const Value &y) {
        return y * x;
    }
};

int main() {
    const double pi = 2 * acos(0);
    
    i32 n;
    cin >> n;
    Vec<double> p(n), q(n), r(n);
    REP(i, n) {
        cin >> p[i] >> q[i] >> r[i];
        r[i] = r[i] / 180 * pi;
    }
    
    SegmentTree<Ops> seg(3 * n, [&](i32 i) -> Matrix<double> {
        Matrix<double> mat(3, 3);
        if (i % 3 == 0) {
            mat(0, 0) = mat(1, 1) = mat(2, 2) = 1.0;
            mat(0, 2) = -p[i / 3];
            mat(1, 2) = -q[i / 3];
        } else if (i % 3 == 1) {
            mat(0, 0) = cos(r[i / 3]);
            mat(0, 1) = -sin(r[i / 3]);
            mat(1, 0) = sin(r[i / 3]);
            mat(1, 1) = cos(r[i / 3]);
            mat(2, 2) = 1.0;
        } else {
            mat(0, 0) = mat(1, 1) = mat(2, 2) = 1.0;
            mat(0, 2) = p[i / 3];
            mat(1, 2) = q[i / 3];
        }
        return mat;
    });
    
    i32 query;
    cin >> query;
    while (query--) {
        i32 s, t;
        double x, y;
        cin >> s >> t >> x >> y;
        --s;
        
        Matrix<double> mat = seg.prod(3 * s, 3 * t);
        Matrix<double> vec(3, 1);
        vec(0, 0) = x;
        vec(1, 0) = y;
        vec(2, 0) = 1.0;
        Matrix<double> ans = mat * vec;
        cout << ans(0, 0) << ' ' << ans(1, 0) << '\n';
    }
}
0