// ===== template.hpp ===== #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #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 using Vec = vector; template bool chmin(T &x, const T &y) { if (x > y) { x = y; return true; } return false; } template 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 > Vec sort_index(i32 n, F f, Comp comp = Comp()) { Vec 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 #include #include // ===== operations.hpp ===== #ifndef OPERATIONS_HPP #define OPERATIONS_HPP #include #include template 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 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 struct Min { using Value = T; static Value id() { return std::numeric_limits::max(); } static Value op(const Value &lhs, const Value &rhs) { return std::min(lhs, rhs); } }; template struct Max { using Value = T; static Value id() { return std::numeric_limits::min(); } static Value op(const Value &lhs, const Value &rhs) { return std::max(lhs, rhs); } }; template 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 struct Reversible { using Value = std::pair; 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 class SegmentTree { public: using Value = typename Monoid::Value; private: std::size_t old_length; std::size_t length; std::vector 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 &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 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 #include #include template class Matrix { std::vector> val; public: Matrix() : val() {} Matrix(std::size_t h, std::size_t w) : val(h, std::vector(w)) {} Matrix(std::size_t h, std::size_t w, const T &ele) : val(h, std::vector(w, ele)) {} Matrix(std::vector> _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 operator+() const { return *this; } Matrix operator-() const { Matrix 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 &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 operator+(Matrix lhs, const Matrix &rhs) { return lhs += rhs; } Matrix &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 operator-(Matrix lhs, const Matrix &rhs) { return lhs += rhs; } Matrix &operator*=(const Matrix &rhs) { *this = *this * rhs; return *this; } friend Matrix operator*(const Matrix &lhs, const Matrix &rhs) { assert(lhs.column() == rhs.row()); Matrix 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 ident(std::size_t n) { Matrix 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 &row : val) { std::swap(row[i], row[j]); } } }; #endif // ===== matrix.hpp ===== struct Ops { using Value = Matrix; 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 p(n), q(n), r(n); REP(i, n) { cin >> p[i] >> q[i] >> r[i]; r[i] = r[i] / 180 * pi; } SegmentTree seg(3 * n, [&](i32 i) -> Matrix { Matrix 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 mat = seg.prod(3 * s, 3 * t); Matrix vec(3, 1); vec(0, 0) = x; vec(1, 0) = y; vec(2, 0) = 1.0; Matrix ans = mat * vec; cout << ans(0, 0) << ' ' << ans(1, 0) << '\n'; } }